private final List<HeapElement> maxHeap;

public MaxHeap(List<HeapElement> listElements) throws Exception {

maxHeap = new ArrayList<HeapElement>();

for (HeapElement heapElement : listElements) {

if (heapElement != null) insertElement(heapElement);

else System.out.println("Null element. Not added to heap");

}

if (maxHeap.size() == 0) System.out.println("No element has been added, empty heap.");

}

// Get the element at a given index. The key for the list is equal to index value - 1

public HeapElement getElement(int elementIndex) {

if ((elementIndex <= 0) && (elementIndex > maxHeap.size())) throw new IndexOutOfBoundsException("Index out of heap range");

return maxHeap.get(elementIndex - 1);

}

// Get the key of the element at a given index

private double getElementKey(int elementIndex) {

return maxHeap.get(elementIndex - 1).getKey();

}

// Swaps two elements in the heap

private void swap(int index1, int index2) {

HeapElement temporaryElement = maxHeap.get(index1 - 1);

maxHeap.set(index1 - 1, maxHeap.get(index2 - 1));

maxHeap.set(index2 - 1, temporaryElement);

}

// Toggle an element up to its right place as long as its key is lower than its parent's

private void toggleUp(int elementIndex) {

double key = maxHeap.get(elementIndex - 1).getKey();

while (getElementKey((int) Math.floor(elementIndex/2)) < key) {

swap(elementIndex, (int) Math.floor(elementIndex/2));

elementIndex = (int) Math.floor(elementIndex/2);

}

}

// Toggle an element down to its right place as long as its key is higher

// than any of its children's

private void toggleDown(int elementIndex) {

double key = maxHeap.get(elementIndex - 1).getKey();

boolean wrongOrder = (key < getElementKey(elementIndex*2)) || (key < getElementKey(Math.min(elementIndex*2, maxHeap.size())));

while ((2*elementIndex <= maxHeap.size()) && wrongOrder) {

// Check whether it shall swap the element with its left child or its right one if any.

if ((2*elementIndex < maxHeap.size()) && (getElementKey(elementIndex*2 + 1) > getElementKey(elementIndex*2))) {

swap(elementIndex, 2*elementIndex + 1);

elementIndex = 2*elementIndex + 1;

}

else {

swap(elementIndex, 2*elementIndex);

elementIndex = 2*elementIndex;

}

wrongOrder = (key < getElementKey(elementIndex*2)) || (key < getElementKey(Math.min(elementIndex*2, maxHeap.size())));

}

}

private HeapElement extractMax() {

HeapElement result = maxHeap.get(0);

deleteElement(0);

return result;

}

@Override

public void insertElement(HeapElement element) {

maxHeap.add(element);

toggleUp(maxHeap.size());

}

@Override

public void deleteElement(int elementIndex) {

if (maxHeap.isEmpty())

try {

throw new EmptyHeapException("Attempt to delete an element from an empty heap");

} catch (EmptyHeapException e) {

e.printStackTrace();

}

if ((elementIndex > maxHeap.size()) && (elementIndex <= 0)) throw new IndexOutOfBoundsException("Index out of heap range");

// The last element in heap replaces the one to be deleted

maxHeap.set(elementIndex - 1, getElement(maxHeap.size()));

maxHeap.remove(maxHeap.size());

// Shall the new element be moved up...

if (getElementKey(elementIndex) > getElementKey((int) Math.floor(elementIndex/2))) toggleUp(elementIndex);

// ... or down ?

else if (((2*elementIndex <= maxHeap.size()) && (getElementKey(elementIndex) < getElementKey(elementIndex*2))) ||

((2*elementIndex < maxHeap.size()) && (getElementKey(elementIndex) < getElementKey(elementIndex*2)))) toggleDown(elementIndex);

}

@Override

public HeapElement getElement() throws EmptyHeapException {

try {

return extractMax();

} catch (Exception e) {

throw new EmptyHeapException("Heap is empty. Error retrieving element");

}

}