package sorting;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.RandomAccess;

import exceptions.EmptyHeapException;

public class SimpleHeapImpl<T> implements Heap<T> {

	private final List<T> heap;
	private final Comparator<T> comparator;

	public SimpleHeapImpl(Comparator<T> comparator) {
		this.comparator = comparator;
		this.heap = new ArrayList<T>();
	}

	public SimpleHeapImpl(List<T> list, Comparator<T> comparator) {
		if (!(list instanceof RandomAccess)) {
			throw new IllegalArgumentException(
					"The list passed has to support random access.");
		}

		this.comparator = comparator;
		this.heap = list;
		heapify();
	}

	public SimpleHeapImpl(T[] array, Comparator<T> comparator) {
		this(new ArrayList<T>(Arrays.asList(array)), comparator);
	}

	@Override
	public int size() {
		return heap.size();
	}

	@Override
	public T peek() throws EmptyHeapException {
		if (heap.isEmpty()) {
			throw new EmptyHeapException();
		}

		return heap.get(0);
	}

	@Override
	public T pop() throws EmptyHeapException {
		if (heap.isEmpty()) {
			throw new EmptyHeapException();
		}

		common.ListUtils.swap(heap, 0, heap.size() - 1);
		T toReturn = heap.remove(heap.size() - 1);
		heapify(0);

		return toReturn;
	}

	@Override
	public void add(T element) {
		heap.add(element);
		heapify();
	}

	private void heapify() {
		for (int rootIndex = parentIndex(heap.size() - 1); rootIndex >= 0; rootIndex--) {
			heapify(rootIndex);
		}
	}

	private void heapify(int rootIndex) {
		heapify(heap.size(), rootIndex);
	}

	private void heapify(int length, int rootIndex) {
		int indexToBeSwapped = rootIndex;

		if (leftChildIndex(rootIndex) < length) {
			if (comparator.compare(heap.get(leftChildIndex(rootIndex)),
					heap.get(indexToBeSwapped)) > 0) {
				indexToBeSwapped = leftChildIndex(rootIndex);
			}
		}

		if (rightChildIndex(rootIndex) < length) {
			if (comparator.compare(heap.get(rightChildIndex(rootIndex)),
					heap.get(indexToBeSwapped)) > 0) {
				indexToBeSwapped = rightChildIndex(rootIndex);
			}
		}

		if (indexToBeSwapped != rootIndex) {
			common.ListUtils.swap(heap, rootIndex, indexToBeSwapped);
			heapify(length, indexToBeSwapped);
		}
	}

	private static int leftChildIndex(int index) {
		return 2 * index + 1;
	}

	private static int rightChildIndex(int index) {
		return 2 * index + 2;
	}

	private static int parentIndex(int index) {
		return new Double(Math.floor((index - 1) / 2)).intValue();
	}

	@Override
	public boolean isEmpty() {
		return size() == 0;
	}

}

@@ -1675,16 +1675,34 @@
 Index;%0A%0A
+%09%09while (true) %7B%0A%09
 %09%09if (le
@@ -1729,32 +1729,33 @@
 ex) %3C length) %7B%0A
+%09
 %09%09%09if (comparato
@@ -1798,32 +1798,33 @@
 otIndex)),%0A%09%09%09%09%09
+%09
 heap.get(indexTo
@@ -1834,32 +1834,33 @@
 wapped)) %3E 0) %7B%0A
+%09
 %09%09%09%09indexToBeSwa
@@ -1889,34 +1889,37 @@
 rootIndex);%0A
+%09
 %09%09%09%7D%0A%09%09
+%09
 %7D%0A%0A
+%09
 %09%09if (rightC
@@ -1947,24 +1947,25 @@
 %3C length) %7B%0A
+%09
 %09%09%09if (compa
@@ -2017,24 +2017,25 @@
 dex)),%0A%09%09%09%09%09
+%09
 heap.get(ind
@@ -2053,24 +2053,25 @@
 ed)) %3E 0) %7B%0A
+%09
 %09%09%09%09indexToB
@@ -2113,18 +2113,21 @@
 x);%0A
+%09
 %09%09%09%7D%0A%09%09
+%09
 %7D%0A%0A
+%09
 %09%09if
@@ -2145,17 +2145,17 @@
 Swapped 
-!
+=
 = rootIn
@@ -2161,16 +2161,33 @@
 ndex) %7B%0A
+%09%09%09%09break;%0A%09%09%09%7D%0A%0A
 %09%09%09commo
@@ -2246,23 +2246,19 @@
 %0A%09%09%09
-heapify(length,
+rootIndex =
  ind
@@ -2266,25 +2266,24 @@
 xToBeSwapped
-)
 ;%0A%09%09%7D%0A%09%7D%0A%0A%09p

Fix heap implementation to use non-recursive heapify.