# Binary Heaps

*Read heaps first.*

## tl;dr

Implementations:

- python:
`heapq`

- java:
`PriorityQueue`

- c++:
`priority_queue`

- ruby: NONE

## Introduction

A binary heap uses a complete binary tree.

Recall that *complete binary trees*:

- have each level filled, with possible exception of last level
- when the last level is incomplete all nodes are filled from the left

**Inserting into a binary heap**:

- place new element in left most spot (n+1)
- "Bubble Up": if and while (new) element dominates parent
- swap them

Swaps happen between levels, and a tree will have lg(n) levels.
Since there are n items to be inserted, insertion will take `O(nlogn)`

.

**Extracting the dominator from a binary heap**:

- remove dominating element from top
- move last added element (bottom-right most leaf) into top
- "Bubble Down": if and while that element does not dominate its children:
- swap it with lesser of two children

### Implementing Binary Heaps

Since a binary heap is a complete binary tree we can implement it using an array.

Example: `2 7 8 1 5 9 3`

pushed into min-heap as a tree:

```
1
2 3
7 5 9 8
```

But as an array looks like: `1,2,3,7,5,9,8,`

.
Notice this is equivalent to a breadth-first traversal.

This image from Wikipedia explains best:

So for some zero-based index `i`

:

- left child =
`2i + 1`

- right child =
`2i + 2`

- parent =
`floor((i-1) / 2)`

*WARNING: Beware zero and one-based version of the above equations.
Many references use one-based equations because the math/logic is cleaner,
but programmers always use zero-based arrays.*

Notice that `floor(n/2)`

is the index of one or more the the middle items of the array:

`floor(n/2)`

if n is odd`floor(n/2)`

and`floor(n/2) - 1`

if n is even

To insert:

- append number to list
"Bubble Up":

`parent = heap[floor((i-1)/2)]`

- if parent < number then swap them

Test your inserts

- Test your removals

Note:

- cannot be efficiently searched because it is not a BST
- we don't know any facts that will improve a linear search

Heap Interface:

- get the dominating element, e.g.
`min`

or`max`

`add`

or`insert`

an element`remove`

or`delete`

an element

We can store any binary tree in an array without pointers but:

- array still requires empty spots for missing nodes
- methods to save memory make it less flexible