Heaps

Bart Massey

Review: Binary Trees

• Graph is connection of nodes and edges

• Binary tree is undirected graph with

  • All nodes connected
  • No cycles
  • All nodes of degree 3 or less

• Rooted binary tree is more common:

  • Distinguished root node
  • Each node may have left and right children

• Full and complete binary tree

  • Call root node depth 0
  • Depth d tree has 2^d+1-1 nodes
  • If not complete, left-pack nodes

• Common representation: downward adjacency list

  • Each node points to left and right child
  • Not super efficient, but super-simple

Array Representation of Full Binary Tree

• Idea: store nodes at array positions with implicit indices

• Root is at index 1 (1-based), left child is at index 2, right at index 3, etc.

         1
        / \
       /   \
      2     3
     / \   /
    4   5 6
  

• In general, left child at 2i, right child at 2i+1

Binary Heap

• Binary Tree with nodes labeled with values of some total-ordered set

• Heap Property: label at any given node is "better" than label of all children

  • = "better" is max-heap

  • <= "better" is min-heap

  • We will work with max-heaps today for reasons to be seen later

         9
        / \
       /   \
      7     6
     / \   /
    3   5 6
    

• Easy to prove largest value is on top (at position 1 in array)

Downheap

• Goal: impose heap property by swapping elements

• If only top elements is out of place, can proceed as follows:

downheap(a, i):
    j ← 2i
    if j > |a|
      return
    if j+1 ≤ a ∧ a[j+1] > a[j]
      j ← j+1
    if a[j] > a[i]
      a[i] ↔ a[j]
      downheap(a, j)

• This "moves the violation down" until bottom

• Tail-recursive, so can be made iterative

• Complexity: O(lg n)

Making A Heap

• Idea: establish heap property bottom-up

heapify(a):
    for i ← |a| downto 1
      downheap(a, i)

• Correctness: By correctness of downheap, ordering

• Complexity: O(|a|) *

Heap Extraction

• Want to get max element from the heap

• Cannot just remove, since that leaves a hole at the top of the heap

• Move the last element of the heap to the top, and shorten the heap

• Use downheap to restore the heap property

• Complexity: O(lg n)

Heapsort

• Sort using min-heap: Repeatedly extract least element, tack on end of new array. O(n lg n) time, O(n) space

• But when extracting, leaves hole at end of array. Can stick extracted element in hole for in-place sorting

• Thus, max-heap does the right thing: inserts elements right-to-left largest-to-smallest in O(lg n) time O(1) space