Max Heap Algorithm
The Max Heap algorithm is a powerful and efficient technique used in computer science for organizing and manipulating data in a binary tree data structure. This algorithm is based on the heap property, which states that the parent node must always have a larger value than its children nodes. In a max heap, every node's value is greater than or equal to the values of its children, with the maximum value residing at the root of the tree. A max heap can be visualized as a complete binary tree where each level, except possibly the last, is completely filled, and all the nodes are as far left as possible.
The main operations performed on a max heap are insertion, deletion, and retrieval of the maximum element. The insertion operation involves adding a new element at the end of the heap and then "bubbling up" the element to its correct position by comparing and swapping with its parent if the element is larger. Deletion of the maximum element (usually the root) involves removing the root, replacing it with the last element in the heap, and then "bubbling down" the new root to its correct position by comparing and swapping with the larger child if the new root is smaller. Retrieval of the maximum element can be done in constant time, as it is always present at the root of the max heap. These operations make the max heap algorithm particularly useful for various applications, including efficient sorting (heapsort), priority queues, and k-largest elements problems.
package DataStructures.Heaps;
import java.util.ArrayList;
import java.util.List;
/**
* Heap tree where a node's key is higher than or equal to its parent's and lower than or equal
* to its children's.
*
* @author Nicolas Renard
*/
public class MaxHeap implements Heap {
private final List<HeapElement> maxHeap;
public MaxHeap(List<HeapElement> listElements) {
maxHeap = new ArrayList<>();
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
*
* @param elementIndex index
* @return heapElement
*/
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.0)) < key) {
swap(elementIndex, (int) Math.floor(elementIndex / 2.0));
elementIndex = (int) Math.floor(elementIndex / 2.0);
}
}
// 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.0))) 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");
}
}
}
