# Binary Heaps & Priority Queues

## #

IntroductionBinary heap (aka priority queue) is an array representation of a heap-ordered **complete** binary tree. Eg: In a min-heap, the root node is minimum element.

A min=heap is *complete binary tree* which is fully filled other than the rightmost elements on the last level. Each node is *smaller* than its children.

Note: All elements must be comparable in a binary heap / priority queue.

### #

When to use a binary heap?We can use a binary heap to get access to the smallest / largest (depends on min / max heap respectively) in constant, `O(1)`

time.

It is widely used for implementations of algorithms like Dijkstra's Shortest Path algorithm and Prim's Minimum Spanning Tree.

## #

DefinitionsA binary heap is a complete binary tree which satisfies the heap ordering property. The ordering can be one of two types:

- the
**min-heap**property: the**value of each node is greater than or equal to the value of its parent**, with the minimum-value element at the root. - the
**max-heap**property: the**value of each node is less than or equal to the value of its parent**, with the maximum-value element at the root.

## #

Properties & Key OperationsHeight of complete tree with N nodes is

`floor(lgN)`

as height only increases when N is a power of 2.Binary heap construction takes linear time,

`O(n)`

3 key operations: Insert, extractMin & getMin. (for a min-heap)

**Insert**: Put new element at**bottom**, and swap with current root**(swim up)**till heap conditions are satisfied.- Time complexity:
`O(log n)`

where n is the number of nodes in heap.

- Time complexity:
**ExtractMin**: Always at the top.- Removing min:
**remove min element**and**swap it with last element**in heap.**Bubble down**this element, swapping with children till heap conditions are satisfied. - Time complexity:
`O(log n)`

- Removing min:
**GetMin**- Return the top element.
- Time complexity:
`O(1)`

Parent's key no smaller than children's keys (max-heap) & vice-versa for min-heap

This means binary heaps can contain duplicate values

Representation:

i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|

a[i] | - | T | S | R | P | N | O | A | E | I | H | C |

- Index
`0`

is not used - Parent of node at
`k`

is at`floor(k/2)`

- Children of node at
`k`

are at`2k`

(left node) and`2k+1`

(right node) - The leaf nodes are at indices from
`floor(n/2) +1`

to`n`

(indices start from 1). - To know the
*maximum*number of nodes at height`h`

, we can use`ceil(n / 2^(h+1))`

. E.g.: For 15 nodes, at height 0, we have`ceil(15 / (2^1)) = 8`

nodes.

Note: See section on Python Basics, for using binary heaps in Python with `heapq`

.