A heap is a specialized tree-based data structure that satisfies the heap property. In a min heap, for any given node i, the value of i is greater than or equal to the value of its parent. This property holds true across the tree. In a max heap, the value of i is less than or equal to the value of its parent.
In this article, we will discuss the implementation of a min heap in Java using an ArrayList. The heap will be able to handle generic types (E) that extend the Comparable interface.
public class Heap<E extends Comparable<E>> {
private List<E> list;
public Heap() {
list = new ArrayList<>();
}
}In the above code, we define a class Heap that takes a generic parameter E which extends Comparable. This means that the elements that we add to the heap must be comparable. We use an ArrayList to store the elements of the heap.
// Time complexity: O(log n)
public void add(E e) {
list.add(e);
int k = list.size() - 1;
// Sifting up the new element to its correct position
while (k > 0 && list.get(k).compareTo(list.get(getParentIndex(k))) < 0) {
swap(k, getParentIndex(k));
k = getParentIndex(k);
}
}In the add method, we add the element e to the end of the list and then sifted up the tree by comparing it to its parent and swapping places if necessary. This ensures that the heap property is maintained, where the root element is always the smallest (or largest) element in the heap.
// Time complexity: O(log n)
public E remove() {
if (list.size() == 0)
throw new RuntimeException("Unable to remove from an empty heap!");
E e = list.get(0);
list.set(0, list.get(list.size() - 1));
list.remove(list.size() - 1);
// Sifting down the element at index 0 to its correct position
int parentIndex = 0;
while (parentIndex < (list.size() / 2)) {
int leftChildIndex = getLeftChildIndex(parentIndex);
int rightChildIndex = getRightChildIndex(parentIndex);
int minIndex = leftChildIndex;
// Finding the smaller of the two children
if (rightChildIndex < list.size() && list.get(leftChildIndex).compareTo(list.get(rightChildIndex)) > 0) {
minIndex = rightChildIndex;
}
// Swapping the parent with the smaller child if necessary
if (list.get(parentIndex).compareTo(list.get(minIndex)) > 0) {
swap(parentIndex, minIndex);
parentIndex = minIndex;
} else {
break;
}
}
return e;
}The remove method removes and returns the smallest element from the heap. It does this by swapping the first and last elements in the list, removing the last element (which is now the smallest element). The new root element is then sifted down the tree by comparing it to its children and swapping places if necessary. This ensures that the heap property is maintained.
The getLeftChildIndex, getRightChildIndex, and getParentIndex methods calculate the indices of a node's left child, right child, and parent, respectively. The swap method swaps the elements at two positions in the list.
private int getLeftChildIndex(int index) {
return 2 * index + 1;
}
private int getRightChildIndex(int index) {
return 2 * index + 2;
}
private int getParentIndex(int index) {
return (index - 1) / 2;
}
private void swap(int first, int second) {
E firstEle = list.get(first);
list.set(first, list.get(second));
list.set(second, firstEle);
}The isEmpty method checks if the heap is empty, and the size method returns the number of elements in the heap.
public boolean isEmpty() {
return this.list.size() == 0;
}
public int size() {
return this.list.size();
}With these methods, our Heap class is complete. We can now add elements to the heap, remove elements from the heap, and check if the heap is empty or not. This implementation of a heap is a fundamental component of many efficient algorithms and data structures. Happy coding! 🚀