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 2d+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(ai):
    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(aj)

  • 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 ← |adownto 1
      downheap(ai)

  • 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