Data Structures and Algorithms Lecture Notes

30 March 2011 • Heaps and Priority Queues

---

Outline

• Array-Based Trees
• Heaps
• Priority Queues

Array-Based Trees

• The array-based implementation of trees is not easily dynamic.
• It is, however, the basis 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.

• How should a tree be packed into an array?

Storing Trees In Arrays

• Ignoring the recursive definition, pack a binary tree into an array by levels.

  

• The ith tree level contains 2ⁱ nodes.
• A node in level i has children in level i + 1.
• How can nodes be located in an array?

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.

Tree-Array Space Requirements

• On the one hand, an array-based tree requires no pointers, eliminating a big overhead.
• On the other hand, array space is allocated level by level.
  • And levels grow exponentially: level i can contain up to 2ⁱ nodes.
• An n-node tree can waste 2^{n - 1} - n space in the worst case.

Heaps

• A heap is a binary tree T satisfying
  1. any node in T has a value at most (or at least) the values stored at its children.
     • This is the heap property.
  2. Leafs in T are in row i, or rows i and i + 1 (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.

• 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 Data Type

• The heap data type 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<T> h1, Heap<T> h2)
  

• Merge one heap into another.

  Heap.merge(Heap<T> h)
  

Heap Data-Type Implementation

• This allows for dynamic arrays.
• At higher expense, Heaps can also be implemented with nodes.

Heap Add

• Add a new element to a heap in two steps:
  1. Add the new element to the end of the heap.

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

Bubble up the new element until it has a larger parent. Or it becomes the root.

• Bubbling up takes O(log n) work.

Example Heap Add

Heap Remove

• Heap remove is restricted to the root.
• Heap remove is both 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

Heap Remove

public T take()
  final T o = heap[0]
  heap[0] = heap[--count]
  pushDown(0)
  return o

private void pushDown(int p)

  final int children [] = 
    new int [] { 2*p + 1, 2*(p + 1) };

  for (int c: children)
    if (c < count) ∧ (heap[p] < heap[c])
      swap(p, c)
      pushDown(c)

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.

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 an efficient basis for priority queues.

---

This page last modified on 2010 November 16.