Heap Data Structure

A heap is a tree-based data structure that maintains properties such that either the maximum or minimum value from a set can be retrieved efficiently.

The two types of heaps are:

Min heap - The root node of each subtree is the smallest element.
Max heap - The root node of each subtree is the largest element.

A heap is a complete binary tree, which means all the levels in the tree are filled (have both left and right nodes), except the last level.

Heap Operations

The 4 main operations of a heap are:

Get min - Get the root element of the heap (the max element in the case of a max heap)
Push - Add an element to the heap. Newly added nodes are placed in the next available position in the tree to maintain its completeness. The node is then swapped with its parent until it is smaller than its children, and the heap property is maintained.
Pop - Remove and retrieve the root element of the heap (the smallest element in a min heap, the largest in a max heap). The heap is reorganized such that the next smallest number becomes the root, maintaining the heap property.
Heapify - Convert an iterable (a list for example) into a heap by reordering the elements.

Heap Big O

Both min and max heaps have the same time complexity. So let's take a look at a min heap Big O:

Operation	Worst Case Time
Insert	O(log n)
Pop	O(log n)
Push	O(log n)
Get min	O(1)

Heap Implementation

In Python, the best way to use a heap is the heapq module.

Heapify

If you want to convert an iterable to a heap:

import heapq

ages = [12, 45, 36, 87, 23]
heapq.heapify(ages)
# ages now fulfills the heap property
print('the smallest number in this min heap is ', ages[0])

1import heapq
2
3ages = [12, 45, 36, 87, 23]
4heapq.heapify(ages)
5# ages now fulfills the heap property
6print('the smallest number in this min heap is ', ages[0])
7

Pop

To pop the smallest number off the heap, we can use heappop()

import heapq

ages = [12, 45, 36, 87, 23]
heapq.heapify(ages)
youngest = heapq.heappop(ages)
print('the youngest persons age is', youngest)

next_youngest = heapq.heappop(ages)
print('now the youngest is ', next_youngest)

1import heapq
2
3ages = [12, 45, 36, 87, 23]
4heapq.heapify(ages)
5youngest = heapq.heappop(ages)
6print('the youngest persons age is', youngest)
7
8next_youngest = heapq.heappop(ages)
9print('now the youngest is ', next_youngest)
10

Push

We can add a new person's age to our heap with heappush()

import heapq

ages = [12, 45, 36, 87, 23]
heapq.heapify(ages)
heapq.heappush(ages, 5)
new_youngest = heapq.heappop(ages)
print('the latest youngest persons age is', new_youngest)

1import heapq
2
3ages = [12, 45, 36, 87, 23]
4heapq.heapify(ages)
5heapq.heappush(ages, 5)
6new_youngest = heapq.heappop(ages)
7print('the latest youngest persons age is', new_youngest)
8

Get min

If we want to just retrieve the smallest number without popping it off, the root is in the first position of a heapified iterable:

import heapq

ages = [12, 45, 36, 87, 23]
heapq.heapify(ages)
youngest = ages[0]
print('the youngest persons age is', youngest)

1import heapq
2
3ages = [12, 45, 36, 87, 23]
4heapq.heapify(ages)
5youngest = ages[0]
6print('the youngest persons age is', youngest)
7

Max heap

Python's heapq operates as a min heap under the hood. To use a max heap, simply negate the values before they enter the heap.

And remember to negate again when reading from the max heap.

import heapq

ages = [12, 45, 36, 87, 23]
# negate before putting into the heap
max_heap = [-1 * age for age in ages]
heapq.heapify(max_heap)

oldest = -1 * max_heap[0]  # negate again to get the original value
print('the oldest persons age is', oldest)

1import heapq
2
3ages = [12, 45, 36, 87, 23]
4# negate before putting into the heap
5max_heap = [-1 * age for age in ages]
6heapq.heapify(max_heap)
7
8oldest = -1 * max_heap[0]  # negate again to get the original value
9print('the oldest persons age is', oldest)
10

9 Essential Trees & Graphs Coding Interview Problems

Master Trees & Graphs by trying the coding challenges below.

1.Inorder TraversalEasy
2.Tree SumEasy
3.Tree HeightEasy
4.LCAMedium
5.Max Path SumHard
6.Search mazeMedium
7.Number of islandsMedium
8.Kth SmallestMedium
9.Sort K ArraysHard

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.