# Binary Heaps & Priority Queues

## Introduction#

Binary 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.

## Definitions#

A 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 Operations#

• Height 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.
• 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)`
• 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:

i01234567891011
a[i]-TSRPNOAEIHC
• 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`.