Data Structures & Algorithms Lecture Notes

3 December 2009 • Heaps and Priority Queues

Outline

Array-Based Trees
Heaps
Priority Queues
Heapsort

Array-Based Trees

The array-based implementation of trees is not easily dynamic.
It is, however, the bases for a number of useful data structures and algorithms.
- It's also a cheap way to implement binary trees in some cases.
- In particular, when the number of elements is bounded.

Storing Trees In Arrays

How should tree nodes be packed into an array?
The ith tree level contains 2ⁱ nodes.
A node in level i has children in level i + 1.

Binary Tree Indexing

binary tree indexing

If a binary-tree node is stored at index i,
- its left child is stored at index 2i + 1 and
- its right child is stored at index 2(i + 1).
The root of the binary tree is stored at index 0.

Heaps

A heap is a binary tree T satisfying
1. the value stored at any node n in T is not less (or greater) than the values stored at n's children.
  - This is the heap property.
2. T is balanced.

Heap Characteristics

A heap's root value is the largest (or smallest) value in the heap.
Heaps and binary search trees are incomparable.
The heap property can be maintained with O(log n) work per element.
Maintaining the heap property is easier than is maintaining the binary search tree property.
- A single pass up or down the heap is enough.

Heap ADT

The heap ADT is stack-like at the interface.
- But no LIFO ordering.
create(), destroy(), … maintenance operations.
add(data) and data remove() manipulation operations.
- Remove only the root.
size(), empty(), data top(), … query operations.

Other Heap Operations

Create a heap containing the contents of an array.
```
heap::create(T a[], unsigned n)
```
- This operation is often called heapify.
Create a heap by merging two other heaps.
```
heap::create(heap h₁, heap h₂)
```
Merge one heap into another.
```
heap::merge(heap h)
```

Heap ADT Implementation

a simple implementation for a heap

This allows for semi-dynamic arrays.

Heap Add

Add a new element to a heap in two steps:


i = count++
d[i] = e
while i ≠ 0
  p = (i - 1)/2
  if d[p] ≥ d[i], break
  swap(d[p], d[i])
  i = p

Add the new element to the end of the heap.
Bubble up the new element until it has a larger parent.

Bubbling up takes O(log n) work.

Example Heap Add

example priority queue enqueue

Heap Remove

Heap remove is restricted to the root.
Heap remove is a simpler and harder than binary-search tree remove.
- Simpler because any leaf may do.
- Harder because the heap property has to be maintained.
Replace the root with a leaf.
Bubble down the root value to maintain the heap property.

Example Heap Remove

example heap remove

Priority Queues

A regular queue stores elements in FIFO order.
Assign each queue element a priority that can be ordered.
A priority queue stores elements in increasing (min queue) or decreasing (max queue) order.
- No more FIFO ordering.
- Sometimes no more end-restricted access either (canceling queued entries).

Heaps as Priority Queues

An array-based heap provides an efficient implementation of a priority queue.
New entries are enqueued at the last element and bubbled up to maintain the heap property.
The head is dequeued by replacing it with the last element and bubbling it down to its proper location.
Heaps provide O(log n) behavior.
- Vs. O(n) for a non-heap implementation.

Sorting Again

Remember this?
A heap can answer these questions at a cost of O(log n) per question.
- That's worst-case O(n log n) total.

Sorting With A Heap

Given an array of elements, heapify it.
- Bubble up successive elements from left to right.
- This costs O(n log n).
Remove the max heap element and store it in the open space.

Heapsort

heapsort(a[], n)

  for i = 1 to n - 1
    bubble-up(a, i)

  for i = n - 1 to 1
    swap(a[0], a[i])
    bubble-down(i)

The constants are worrisome.

Are They?

heapsort vs quicksort on ints

heapsort vs quicksort on points

Apparently.

Summary

The heap property means parents are at least (or most) their children.
- The heap property is different from the binary-search property.
A heap is a binary tree obeying the heap property.
Array-implemented heaps are common.
- Simple, fast, small.
Heaps are the basis for priority queues and heapsort.

References

Algorithm 232: Heapsort by J.W.J Williams, Communications of the ACM, June 1964.