A binary heap is binary tree structure that typically uses an array as its underlying data structure. Heaps are one of the fundamental data structures that all software developers should have in their toolkit due to the fast extraction of either a minimum or a maximum element.
Heaps come in two flavours, the min-heap which allows quick \(O(\log n)\) extraction of the minimum element, and the max-heap which allows the same for the maximum value. Before it is possible to extract values, the heap must first be constructed. This is done by going through the first half of the elements (in the array) starting from the middle and calling 'heapify' on each element, running in \(O(n)\) time.
It is typical to implement priority queues using heaps due to their \(O(\log n)\) extract min/max time.
Time complexity
| Operation | Description | Complexity |
|---|---|---|
| Decrease key | Decreases an existing key to some value | \(Θ(\log n)\) |
| Delete | Deletes a node given a reference to the node | \(Θ(\log n)\) |
| Extract minimum | Removes and returns the minimum value given a reference to the node | \(Θ(\log n)\) |
| Find minimum | Returns the minimum value | \(Θ(1)\) |
| Insert | Inserts a new value | \(Θ(\log n)\) |
| Union | Combine the heap with another to form a valid binomial heap | \(Θ(n)\) |
Operations
All operations will use min-heap as an example.
Heapify(i)
smallest ← smallest child of node if smallest exists and is less than node swap node with smallest in the list minHeapify(node)
Build heap
for i ← floor(list's size / 2) to 0 heapify(i)
Insert(item)
add item to end of list while item's parent exists and item is less than parent swap(item, parent)
ExtractMin / ExtractMax
if list's size is 0 return null if list's size is 1 remove and return only element min ← list[0] list[0] ← last element of list heapify(0) return min
Heapsort
Heapsort operates by forming a heap, extracting the min/max item and repeating on the smaller array until everything is sorted. This can be done in-place by heapifying and then incrementing the start index of the array. Heapsort runs in \(O(n \log n)\) time. This algorithm is explained in depth in the Heapsort article.
Code
Here is a full generic implementation of a min-heap. Notice that the only changes needs to be made to turn this into a max-heap are symbol names and the marked comparisons.
public class MinHeap<T extends Comparable<T>> {
private ArrayList<T> list;
public MinHeap() {
this(0);
}
public MinHeap(int size) {
list = new ArrayList<T>(size);
}
public MinHeap(ArrayList<T> items) {
list = items;
buildHeap();
}
public void insert(T item) {
int i = list.size();
list.add(item);
int parent = parent(i);
while (parent != i && list.get(i).compareTo(list.get(parent)) < 0) {
swap(i, parent);
i = parent;
parent = parent(i);
}
}
public T extractMin() {
if (list.size() == 0)
return null;
if (list.size() == 1)
return list.remove(0);
T min = list.get(0);
T last = list.remove(list.size() - 1);
list.set(0, last);
heapify(0);
return min;
}
public T min() {
return list.get(0);
}
public boolean isEmpty() {
return list.size() == 0;
}
public int size() {
return list.size();
}
public void print() {
for (int i = 0; i < list.size(); i++)
System.out.print(list.get(i) + ", ");
System.out.println();
}
private void buildHeap() {
for (int i = (int)(list.size() / 2); i >= 0; i--)
heapify(i);
}
private void heapify(int i) {
int left = left(i);
int right = right(i);
int small = i;
if (left < list.size() && list.get(left).compareTo(list.get(i)) < 0)
small = left;
if (right < list.size() && list.get(right).compareTo(list.get(small)) < 0)
small = right;
if (small != i) {
swap(i, small);
heapify(small);
}
}
private void swap(int i1, int i2) {
T temp = list.get(i1);
list.set(i1, list.get(i2));
list.set(i2, temp);
}
private int parent(int i) {
return i / 2;
}
private int left(int i) {
return 2 * i;
}
private int right(int i) {
return 2 * i + 1;
}
}