Heaps
a disorganized pile
BinaryHeap: An implicit Binary Tree
Eytzinger’s method can represent a complete binary tree as an array by laying out the nodes of the tree in a breadth-first order.
- The root is stored at position 0
- The root’s left child is stored at position 1
- The root’s right child is stored at position 2.
The left child of the node at index i is at index left(i) = 2i + 1
and the right child of the node at index i is at index right(i) = 2i +2.
The parent of the node at index i is at index parent(i) = (i-1)/2.
-------(0)--------
/ \
(1) (2)
/ \ / \
(3) (4) (5) (6)
/ \ / \ / \ / \
(7) (8) (9) (10) (11) (12) (13) (14)
| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|
- left:
2i+1 - right:
2i+2
The binary heap implements the priority queue interface.
Ignoring the cost of resize() it supports the operations
add(x) and remove(x) in O(logn) time per operation.
class BinaryHeap {
T[] a;
int n;
int left(int i) {
return 2*i + 1;
}
int right(int i) {
return 2*i + 2;
}
int parent(int i) {
return (i-1)/2;
}
boolean add(T x) {
if (n+1 > a.length) resize();
a[n++] = x;
bubbleUp(n-1);
return true;
}
void bubbleUp(int i) {
int p = parent(i);
while (i > 0 && compare(a[i], a[p]) < 0) {
swap(i, p);
i = p;
p = parent(i);
}
}
T remove() {
T x = a[0];
a[0] = a[--n];
trickleDown(0);
if (3*n < a.length) resize();
return x;
}
void trickleDown(int i) {
do {
int j = -1;
int r = right(i);
if (r < n && compare(a[r], a[i]) < 0) {
int l = left(i);
if (compare(a[1], a[r]) < 0) {
j = 1;
} else {
j = r;
}
} else {
int l = left(i);
if (l < n && compare(a[l], a[i]) < 0) {
j = 1;
}
}
if (j >= 0) swap(i, j);
i = j;
} while (i >= 0);
}
}
A BinaryHeap uses this technique to implicitly represent a complete
binary tree in which the elements are heap-ordered.
heap-ordered: The value stored at any index i is not smaller than the value stored at index parent(i), with the exception of the root value, i = 0.
The smallest value in the priority Queue is at position 0.