Solve 25 questions to master Heap Data Structure patterns

3 min readFeb 2, 2021

This post is to deep dive into one of the most fundamental data structures called Heap. The objective of this post is to understand the basics of Heap. time complexities, and identify patterns when to use Heap as a data structure.

What is Heap?

It is mainly used to represent a priority queue.
It is represented as a Binary Tree (a tree structure where a node of a tree has a maximum of two child nodes). Heaps are complete binary trees.
A simple array can be used to represent a Heap where array indices refer to the node position in the tree.
Parent and child nodes can be accessed with indices:
* A root node｜i = 0, the first item of the array
* A parent node｜parent(i) = i / 2
* A left child node｜left(i) = 2i
* A right child node｜right(i)=2i+1
Two type of Heaps — Min Heap, Max Heap
Min Heap — the parent node always has a smaller value than the child nodes.
Max Heap — the parent node is always larger than the child node value.
Usually, when a type is not mentioned, it refers to the MinHeap. Python Heap has minHeap as default.
In python, theheapqmodule provides the basic features for Heap data structure.
minHeap are used in tasks related to scheduling or assignment. A more detailed explanation is under the Patterns section below.

Heap Operations

The basic operations in Python heapq are:

heapify

The heapify operation converts the iterable array heap into a tree structure w.r.t heap order.

heappush

It inserts an element into the heap. Post insertion the heap order is adjusted to maintain the heap properties.

import heapq as hq# Simple array is heap
minHeap = []# Adding an element to the heap
hq.heappush(minHeap, 5)

heappop

This operation is to remove the element from the heap. By default it is minHeap, so this operation removes the min element from the minHeap. And for maxHeap, it is the maximum element. Post removal, heapify is called internally to maintain the heap order.

import heapq as hqminHeap = [5, 6, 2]# this is done to convert iterable into a heap tree
hq.heapify(minHeap) # Getting top element from the heap
value = hq.heappop(minHeap) # the value here is 2 as 2 is the minimum value.

Other operations in heapq python module includes heappushpop ,heapreplace , nlargest , nsmallest .