Skip to main content

Heap

What is a Heap?​

A Heap is a complete binary tree that satisfies the heap property.

Complete Binary Tree​

  • All levels are fully filled except possibly the last.
  • The last level is filled from left to right.
        10
       /  \
      8    9
     / \  /
    3  5 6

This property allows heaps to be efficiently stored in arrays.

Types of Heap​

Max Heap​

Parent node is greater than or equal to children.

        50
       /  \
      30   40
     / \   /
    10 20 35

Largest element = root

Used for:

  • Finding maximum
  • Heap Sort
  • Top K largest elements

Min Heap​

Parent node is smaller than or equal to children.

        10
       /  \
      20   30
     / \   /
    40 50 60

Smallest element = root

Used for:

  • Priority Queue
  • Dijkstra
  • Merge K sorted lists

Array Representation of Heap​

Heaps are usually stored in arrays.

For index i

Left child  = 2*i + 1
Right child = 2*i + 2
Parent      = (i-1)/2

Example heap:

        10
       /  \
      20   30
     / \
    40 50

Array representation:

[10,20,30,40,50]

Indexes:

0
1   2
3 4

Basic Heap Operations​

Important operations:

  1. Insert
  2. Delete
  3. Heapify
  4. Peek
  5. Extract Min / Max
  6. Build Heap

Insert Operation​

Steps:

  1. Insert element at end of heap
  2. Heapify up (bubble up)

Example: Insert 15

Initial Min Heap

        10
       /  \
      20   30

Insert:

        10
       /  \
      20   30
     /
    15

Heapify up:

        10
       /  \
      15   30
     /
    20

Time Complexity

O(log n)

Delete Operation​

Usually delete the root.

Steps:

  1. Replace root with last element
  2. Remove last node
  3. Heapify down

Example:

Min Heap

        5
       / \
      10  15
     /
    20

Delete root:

Replace with 20

        20
       / \
      10  15

Heapify down:

        10
       / \
      20  15

Time complexity

O(log n)

Heapify Operation​

Heapify restores heap property.

Two types:

Heapify Up​

Used in insert

Heapify Down​

Used in delete

Example heapify down:

        30
       /  \
      10   20

After heapify:

        10
       /  \
      30   20

Time complexity:

O(log n)

Build Heap​

Convert an array into heap.

Efficient method:

Start from last non-leaf node.

Formula:

last_non_leaf = n/2 - 1

Example:

Array

[10,5,20,2,8]

Build min heap

        2
       / \
      5   20
     / \
    10 8

Time Complexity:

O(n)

Important interview trick:

Build heap is O(n) not O(n log n).

Extract Min / Max​

Remove root and return it.

Steps:

  1. Save root
  2. Replace root with last element
  3. Heapify down

Time complexity

O(log n)

Priority Queue​

Most languages implement heap using Priority Queue.

priority_queue<int> maxHeap;

priority_queue<int, vector<int>, greater<int>> minHeap;

Heap Sort​

Heap Sort uses Max Heap.

Steps:

  1. Build Max Heap
  2. Swap root with last element
  3. Reduce heap size
  4. Heapify

Example:

Array

[4,10,3,5,1]

Sorted:

[1,3,4,5,10]

Complexity:

Time: O(n log n)
Space: O(1)

Advantage:

  • In-place
  • No extra memory