Stack Bash - Master data structures and algorithms

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:
  1. Min heap - The root node of each subtree is the smallest element.
  2. 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:
  1. Get min - Get the root element of the heap (the max element in the case of a max heap)
  2. 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.
  3. 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.
  4. 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:
OperationWorst Case Time
InsertO(log n)
PopO(log n)
PushO(log n)
Get minO(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:

Pop

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

Push

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

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:

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.

9 Essential Trees & Graphs Coding Interview Problems

Master Trees & Graphs by trying the coding challenges below.
  1. 1.Inorder TraversalEasy
  2. 2.Tree SumEasy
  3. 3.Tree HeightEasy
  4. 4.LCAMedium
  5. 5.Max Path SumHard
  6. 6.Search mazeMedium
  7. 7.Number of islandsMedium
  8. 8.Kth SmallestMedium
  9. 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.