Saturday, 26 January 2013

Binary heap

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

OperationDescriptionComplexity
Decrease keyDecreases an existing key to some value$Θ(\log n)$
DeleteDeletes a node given a reference to the node$Θ(\log n)$
Extract minimumRemoves and returns the minimum value given a reference to the node$Θ(\log n)$
Find minimumReturns the minimum value$Θ(1)$
InsertInserts a new value$Θ(\log n)$
UnionCombine 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
list ← 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.

View on GitHub

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();
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;
}
}