# 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):
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