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.