Heap Data Structure

Heaps are a data structure for supporting the priority queue operations insert and find-minimum. They work by maintaining a partial order on the set of elements that is weaker than the sorted order (so it can be efficient to maintain), yet stronger than random order (so the minimum element can be quickly identified).

---

Heap-Labeled Tree

A heap-labeled tree is defined to be a binary tree such that the key of each node dominates the keys of its children.

• In a min-heap, a node dominates its children by having a smaller key than they do
• In a max-heap, a node dominates its children by having a bigger key than they do

The most natural implementation of this binary tree would store each key in a node with pointers to its two children. However, similar to binary search trees, the memory used by the pointers can easily outweigh the size of keys, which is the data we’re mostly interested in.

Sometimes, “heap” is used to refer to a heap-labeled tree.

---

Heap Array

The heap is a slick data structure that enables us to represent binary trees without using any pointers. We store data as as an array of keys, and use the position of the keys to implicitly play the role of pointers. We assume that the array starts with index 1 for simplicity.

We store the root of the tree at the first position of the array, and its left and right children in the second and third positions. In general, we store the $2^{l-1}$ keys of the $l$th level of a complete binary tree from left to right in positions $2^{l-1}$ to $2^l-1$, as shown above.

• Level 1 (1492): $2^{1-1}=1$ key, stored at position $2^{1-1}=1$
• Level 2 (1783, 1776): $2^{2-1}=2$ keys, stored between positions $2^{2-1}=2$ and $2^2-1=3$
• Level 3 (1804, 1865, 1945, 1963): $2^{3-1}=4$ keys, stored between positions $2^{3-1}=4$ and $2^3-1=7$.

What is especially nice about this representation is that the positions of the parent and children of the key at position $k$ are readily determined. Thus, we can move around the tree without any pointers.

• The left child of $k$ sits in position $2k$ and the right child in $2k+1$
• The parent of k holds court in position $\lfloor k/2\rfloor$ .

typedef struct { 
	item_type q[PQ_SIZE+1]; /* body of queue */ 
	int n;                  /* number of queue elements */ 
} priority_queue;

typedef struct { 
	item_type q[PQ_SIZE+1]; /* body of queue */ 
	int n;                  /* number of queue elements */ 
} priority_queue;
 
int pq_parent(int n) {
	if (n == 1) { 
		return(-1); 
	} 
	return((int) n/2); /* implicitly take floor(n/2) */ 
}
 
int pq_young_child(int n) { 
	return(2 * n); 
}

This approach means that we can store any binary tree in an array without pointers. What is the catch? Suppose our height $h$ tree was sparse, meaning that the number of nodes $n\ll 2^h-1$. All of the missing internal nodes still take up space in our structure, since we must represent a full binary tree to maintain the positional mapping between parents and children.

To avoid these holes and ensure space efficiency, we make each level be packed as much as it can be, such that:

• Only the last level may be incomplete.
• The elements of the last level as far left as possible.

Thus, we can represent an $n$-key tree using the first $n$ elements of the array. If we did not enforce these structural constraints, we might need an array of size $2n-1$ to store $n$ elements.

With heaps, all but the last level are filled, so the height $h$ of an $n$ element heap is logarithmic because:

$$\begin{array}{rl}\sum _{i=0}^{h-1}{2}^i=2^h-1& \ge n\\ 2^h& \ge n+1\\ h& =\lceil {\log }_2(n+1)\rceil \end{array}$$

Benefits/Drawbacks

This implicit representation of binary trees saves memory, but is less flexible than using pointers.

• We cannot store arbitrary tree topologies without wasting large amounts of space.
• We cannot move subtrees around by just changing a single pointer, only by explicitly moving all the elements in the subtree.

This loss of flexibility explains why we cannot use this idea to represent binary search trees, but it works just fine for heaps.

How can we efficiently search for a particular key $k$ in a heap? We can’t. Binary search does not work because a heap is not a binary search tree, and the array form of the heap is not sorted. We know almost nothing about the relative order of the $n/2$ leaf elements in a heap that would let us avoid doing linear search through them.

Heap Construction

Heaps can be constructed incrementally, by inserting each new element into the left-most open spot in the array ($(n+1)$st position of a previously $n$-element heap). This ensures the desired balanced shape of the heap-labeled tree, but does not maintain the dominance ordering of the keys. The new key might be less than its parent in a min-heap, or greater than its parent in a max-heap, which we don’t want.

The solution to this is to swap any dissatisfied element with its parent:

• The old parent is now happy, as it is properly dominated
• The other child of the old parent is happy, because it is now dominated by an element even more extreme than before
• The new element is now happier, but may still dominate its new parent. So we recur at a higher level, bubbling up the new key to its proper position in the hierarchy.
  • Since we replace the root of a subtree by a larger one at each step of bubbling up, we preserve the heap order elsewhere.

void pq_insert(priority_queue *q, item_type x) {
 
	if (q->n >= PQ_SIZE) { // q->n dereferences pointer and accesses member of the struct it points to. Equivalent to (*q).n
		printf("Warning: priority queue overflow! \n");
	}
	else {
		q->n = (q->n) + 1; 
		q->q[q->n] = x;
		bubble_up(q, q->n);
	}
}
 
void bubble_up(priority_queue *q, int p) {
 
	if (pq_parent(p) == -1){
		return;
	}
 
	if (q->q[pq_parent(p)] > q->q[p]) {
		pq_swap(q, p, pq_parent(p));
		bubble_up(q, pq_parent(p));
	}
 
}

This swap process takes constant time at each level. Since the height of an $n$-element heap is ${\log }_{2}n$, each insertion takes at most $O(\log n)$ time. A heap of $n$ elements can thus be constructed in $O(n\log n)$ time through $n$ such insertions:

void pq_init(priority_queue *q) {
	q->n = 0
}
 
void make_heap(priority_queue *q, item_type s[], int n) {
	int i;
	pq_init(q);
 
	for (i = 0; i < n; i++){
		pq_insert(q, s[i]);
	}
}

Find and Delete Min/Max

The remaining priority queue operations are identifying and deleting the dominant element (min or max). Identification is easy, since the top of the heap sits in the first position of the array.

Removing the top elements leaves a hole in the array, which can be filled by moving the right-most leaf (sitting in the $n$th position of the array) into the first position. This restores the shape of the tree, but the labeling of the root might not satisfy the heap property. The new root might be dominated by both of its children.

For example, the root of a min-heap should be the smallest of 3 elements: the current root and its 2 children. The cases are:

• If the current root is dominant, the heap order has been restored.
• If not, the dominant child should be swapped with the root, and the problem is pushed down to its next level.

The dissatisfied element bubbles down the heap until it dominates all its children. This operation is called heapify, because it merges two heaps (the subtrees below the original root) with a new key.

item_type extract_min (priority_queue *q) {
	int min = -1;
	
	if (q->n <= 0){
		printf("Warning: empty priority queue. \n")
	}
	
	else{
		min = q->q[1];
		q->q[1]= q->q[q->n];
		q->n = q->n - 1;
		bubble_down(q, 1);
	}
 
	return min;
}
 
void bubble_down(priority_queue *q, int p){
	int c; // child index
	int i; // counter
	int min_index; // index of lightest child
 
	c = pq_young_child(p);
	min_index = p;
 
	for (i = 0; i <= 1; i++) {
		if ((c+1) <= q->n) {
			if (q->q[min_index] > q->q[c+i]) {
				min_index = c + i;
			}
		}
	}
	if (min_index != p) {
		pq_swap(q, p, min_index);
		bubble_down(q, min_index);
	}
}

We will reach a leaf after $\lfloor {\log }_{2}n\rfloor$ steps of bubble_down, each constant time. Thus, root deletion is completed in $O(\log n)$ time.

Repeatedly exchanging the maximum element with the last element and caling heapify yields an $O(n\log n)$ sorting algorithm, heapsort.

Faster Heap Construction

As we saw previously, a heap can be constructed on $n$ elements by incremental insertion in $O(n\log n)$ time. We can actually construct them even faster by using our bubble_down procedure above.

Suppose we pack $n$ keys into the first $n$ elements of our priority queue array. The shape of our heap will be right, but the dominance order will be wrong. How can we restore it?

Consider the array in reverse order, starting from the last ($n$th) position. It represents a leaf of the tree and so dominates its non-existent children. The same is the case for the last $n/2$ positions in the array, because all are leaves. If we continue to walk backwards through the array we will eventually encounter an internal node with children. This element may not dominate its children, but its children represent well-formed (if small) heaps.

This is exactly the situation the bubble_down procedure was designed to handle, restoring the heap order of an arbitrary root element sitting on top of two sub-heaps. Thus, we can create a heap by performing $n/2$ non-trivial calls to the bubble down procedure:

void make_heap_fast(priority_queue *q, item_type s[], int n){
	int i;
 
	q->n = n;
	for (i = 0; i < n; i++){
		q->q[i + 1] = s[i];
	}
 
	for (i = q->n/2; i >= 1; i--){
		bubble_down(q, i);
	}
}

Multiplying the number of calls to bubble down ($n$) times an upper bound on the cost of each operation ($O(logn)$) gives us a running time analysis of $O(n\log n)$. This would make it the same speed as the incremental insertion algorithm described above. But note that it is indeed an upper bound, because only the last insertion will actually take $\lg n$ steps. Recall that bubble down takes time proportional to the height of the heaps it is merging. Most of these heaps are extremely small. In a full binary tree on $n$ nodes, there are $n/2$ nodes that are leaves (i.e. height 0), $n/4$ nodes that are height 1, $n/8$ nodes that are height 2, and so on. In general, there are at most $\lceil n/2h+1\rceil$nodes of height $h$, so the cost of building a heap is:

$$\sum _{h=0}^{\lceil \lg n\rceil }\lceil n/2^{h+1}\rceil h\le n\sum _{h=0}^{\lceil \lg n\rceil }h/2^h\le 2n$$

Since this sum is not quite a geometric series, we can’t apply the usual identity to get the sum, but the puny contribution of the numerator ($h$) is crushed by the denominator ($2^h$). The series quickly converges to linear.

Does it matter that we can construct heaps in linear time instead of $O(n\log n)$? Not really. The construction time did not dominate the complexity of heapsort, so improving the construction time does not improve its worst-case performance. Still, it is an impressive display of the power of careful analysis, and the free lunch that geometric series convergence can sometimes provide.