## Heap

a container that have keys

key property: at every node $x$

- key[x] $\leqslant$ (or $\geqslant$) all keys of $x$'s children
- therefore, the object at root must have min (max) value

## operations

insert

- adds new object
- $O(\log n)$

extract-min(max)

- extracts min (max) from heap
- ties broken arbitrarily
- $O(\log n)$

heapify

- initialization: builds a heap

delete

## Implementation

- it's a tree with [math]\approx \log_2 n[/math] levels
- backed by array

Traversing the tree:

- [math]\text{parent}(i) = i / 2[/math]
- [math]\text{left}(i) = 2i[/math]
- [math]\text{right}(i) = 2i + 1[/math]

insert(key $k$):

- stick $k$ at the end of last level
- bubble-up $k$ until heap property is restored

extract-min():

- delete root
- move last leaf to be new root
- bubble-down until heap property is restored
- (always swap with the smallest child)

Java implementation:

## Applications

- general: fast way to do repeated minimum (maximum) computations
- priority queues, "event manager"

### Heap sort

- put everythin into heap
- repeatedly extract-min until the heap is empty

### Median maintenance

- given: a sequence of numbers $x_1, ..., x_n$, one-by-one
- goal: at each time step $i$, compute the median of $\{x_1, ..., x_i\}$
- solution:
- create two heaps:
- $H_\text{low}$ (with extract-max operation),
- $H_\text{high}$ (extract-min)

- key idea: maintain invariant that $\approx \cfrac{i}{2}$ smallest (largest) numbers are in $H_\text{low}$ ($H_\text{high}$)
- so on $20$th step, in $H_\text{low}$ would be $10$th order statistics, and in $H_\text{high}$ - $11$th
- keep the heaps balanced! (so they have the same number of elements)

Implementation: [1]

- naive $\Theta(nm)$
- with heaps $O(m \log n)$

## See also

## Sources