# 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

ifj> |a|

return

ifj+1 ≤a∧a[j+1] >a[j]

j←j+1

ifa[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):

fori← |a|downto1

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