Heaps

We can think of a heap as an array with a special property: the smallest value in the array is always in the first index of the array.

If we remove the smallest value from the heap, the elements of the array efficiently re-arrange so that the next smallest value takes its place at the front of the array.

Heaps are most frequently used in coding interviews to solve a class of problems known as "Top K" problems, which involve finding the k smallest or largest elements in a collection of elements.

This module prepares you to use heaps during the coding interview by covering:

How heaps are able to achieve their special property efficiently, which enable you to discuss heaps effectively during the interview.
How to use heaps in Python.
The types of coding interview questions that are best solved using heaps.

Heap Properties

Although we can think of a heap as an array, it's more helpful to visualize a heap as a binary tree. For example, we can visualize the heap [1, 2, 4, 5, 8, 6, 9] like this:

The elements correspond to a level-order traversal of the binary tree. The root of the binary tree is stored at index 0, its left and right children are stored at indices 1 and 2, respectively, and so on.

The array representation is shown above the heap. Each node in the binary tree is labeled with the corresponding index in the array.

These two representations of a heap are equivalent. The binary tree representation is a more intuitive way to understand how a heap works. But during the coding interview, you will most likely be working with the array representation of a heap, as it more efficient to work with.

Our heap is a min-heap because the smallest value in the heap is at the root node (compare that to a max-heap, in which the largest value is at the root).

The binary tree satisfies the heap property: each node in the tree has a value that is less than or equal to the values of both its children.

Node 2 has a value that is less than both its children (5 and 8).

Any binary tree that satisfies the heap property is a heap:

Left: A valid heap, right: an invalid heap.

Heaps are complete binary trees, which means that all levels of the tree are fully filled except for the last level, which is filled from left to right.

Left: A valid heap, right: an invalid heap.

Since heaps are complete binary trees, the height of a heap is O(log n), where n is the number of elements in the heap. This is an important property to keep in mind when analyzing the time complexity of heap operations.

Max Heap

The heap property for a max heap is that each node has a value that is greater than or equal to the values of both its children.

Parent-Child Relationship

We can express the parent-child relationships of the binary tree representation of a heap using the indexes of the array. Given a node at index i in the array:

Node	Index
Left Child	2 * i + 1
Right Child	2 * i + 2
Parent	⌊(i - 1) / 2⌋ (floor division)

For example, for the node at index i = 2:

The left child is at index 2 * 2 + 1 = 5:
The right child is at index 2 * 2 + 2 = 6:
The parent is at index ⌊(2 - 1) / 2⌋ = 0:

Heap Operations

A heap supports the following operations:

push(element): Add a new element to the heap.
pop(): Remove the root element from the heap.
peek(): Get the root element without removing it.
heapify([elements]): Convert an array into a heap in-place.

We'll learn about each of these operations on a min-heap by visualizing how both the array and binary tree representation of a heap change after each operation. Doing so will help us understand the time complexity of each operation.

We omit the acutal code implementation for these operations, as Python provides a built-in heapq module that you can use to create and manipulate heaps during your interviews.

However, understanding how the operations work conceptually allow you to discuss heaps at the level required for the interview. In particular, you need to know how these operations allow the heap to efficiently maintain the heap property.

Push

The push operation takes a new element and adds it to the heap. The element is added in a way such that the heap property is maintained.

We'll visualize each step of how the heap on the left changes after we add a new value of 3:

Step 1: Add the new element to the next available position in the last level of the tree.

Step 2: "Bubble Up" Compare the new element with its parent. If the new element is less than its parent, swap the two elements. Repeat this process until the new element is greater than its parent, or until it reaches the root of the heap.

Since the new element 3 is less than its parent 5, we swap the two values.

Time Complexity

The time complexity of the push operation is O(log n), where n is the number of items in the heap.

In the worst case, the new element will start at the last level of the tree and will "bubble-up" to the root, which takes O(log n) swaps, or the height of the tree. Since we are swapping indexes in an array, each swap operation takes O(1) time.

Pop

The pop operation removes and returns the minimum value from the heap. When the pop operation is complete, the new root of the heap is the new minimum value in the heap, and the heap property is restored.

We'll visualize each step of how the heap on the left changes after we remove the root element (1):

Step 1: Remove the root element from the heap, and replace it with the last element in the heap (the rightmost node in the last level).

Replacing the root with Node 3.

Step 2: "Bubble Down" Compare the new root with its children. If the new root is greater than either of its children, swap the root with the smaller of the two children. Repeat this process until the new root is less than both of its children, or until it reaches the last level of the heap.

Swapping the new root with Node 2.

Time Complexity

The time complexity of the push operation is O(log n), where n is the number of items in the heap.

In the worst case, after removing the root element, the new root starts at the top of the tree and "bubbles-down" to the last level of the tree, which takes O(log n) swaps, or the height of the tree.

Peek

The peek operation returns the minimum value in the heap without removing it. The minimum value is always the root of the heap.

Time Complexity O(1): The peek operation has a constant time complexity since it only involves accessing the root of the heap, which is always index 0 in the array.

Heapify

The heapify operation takes a list of elements and converts it into a heap in O(n) time.

We'll start with [4, 6, 9, 3, 2, 8, 3] and convert it into a heap using the heapify operation:

The given array represented as a binary tree. Note this not yet a heap!

Step 1 Starting with the first non-leaf node (the parent of the last element in the array), compare the node with its children. If the node is greater than either of its children, swap the node with the smaller of the two children.

Starting with Node 9, we swap it with Node 3. The highlighted subtree is now a min-heap.

Step 2 Move to the next non-leaf node and repeat the process until the root of the tree is reached.

Moving onto Node 6, we swap it with Node 2. At this point, both the left and right subtrees of the heap are valid min-heaps.

Move to the root node, swap it with Node 2. At this point, the left subtree is not a valid min-heap.

Move to node 4, and swap it with Node 3. Our heap is now a min heap!

Time Complexity

O(n). The formal proof for the time complexity of the heapify operation is very math heavy, and beyond the scope of coding interviews, and thus, this lesson as well. If you're interested in learning more about the time complexity of the heapify operation, you can refer to the Wikipedia page.

Summary

If you only takeaway one thing from this section, remember that the pop and push operations both have a time complexity of O(log n). The worst case for each operation involves swapping elements from the root of the heap to the last level of the tree, or vice versa, which takes O(log n) time.

Operation	Time Complexity	Notes
pop	O(log n)	Visualize bubbling down the new root to the last level of the tree.
push	O(log n)	Visualize bubbling up the new element to the root of the tree.
peek	O(1)	Access the root of the heap.
heapify	O(n)	Just memorize this!

Python HeapQ Module

Python provides a built-in module called heapq that we can use to turn arrays into min-heaps.

The heapify function can be used to convert an array into a heap in-place. The heappush and heappop functions are used to push and pop elements from the heap, respectively.

Usage

import heapq

arr = [3, 1, 4, 1, 5, 9, 2]

# convert array into a heap in-place. O(n)
heapq.heapify(arr)

# push 0 to the heap. O(log n)
heapq.heappush(arr, 0)

# peek the min element = 0. O(1)
arr[0]

# pop and return the min element = 0. O(log n)
min_element = heapq.heappop(arr)

# peek the new min element = 1. O(1)
arr[0]

Max Heap

By default, the heapq module creates a min-heap. To create a max-heap, we can negate the values in the list and then convert it into a heap using the heapify function. We also need to remember to negate the values when we push and pop elements from the heap.

import heapq

arr = [3, 1, 4, 1, 5, 9, 2]

# negate the values in the array
negated_arr = [-x for x in arr]

# convert array into a min-heap
heapq.heapify(negated_arr) 

# push 11 to the heap by negating it
heapq.heappush(negated_arr, -11)

# peek root of heap = -11
negated_arr[0]

# pop and return the max element = -11
max_element = -heapq.heappop(negated_arr)

# peek the new max element = 9
negated_arr[0]

Storing Tuples

The heapq module can also be used to store tuples in the heap. By default, the heap is ordered based on the first element of the tuple. If the first elements are equal, the second elements are compared, and so on.

import heapq

arr = [(3, 1), (1, 5), (4, 2), (1, 9), (5, 3), (9, 4), (2, 6)]
heapq.heapify(arr)

# pop and return the min element = (1, 5)
min_element = heapq.heappop(arr)

# peek the new min element = (1, 9)
arr[0]

# push (1, 7) to the heap, which is smaller than (1, 9)
heapq.heappush(arr, (1, 7))

# peek the min element = (1, 7)
arr[0]

Use Case

Top-K Largest Elements in an Array

Heaps are useful for solving problems that require finding the "top k" elements in an array. For example, let's use a heap to find the 3 largest elements in an array.

DESCRIPTION

Given an integer array nums, return the 3 largest elements in the array in any order.

Example


Input: nums = [9, 3, 7, 1, -2, 6, 8]
Output: [8, 7, 9]
# or [7, 9, 8] or [9, 7, 8] ...

Here's how we can solve this problem using a min-heap:

Create a min-heap that stores the first 3 elements of the array. These represent the 3 largest elements we have seen so far, with the smallest of the 3 at the root of the heap.

Iterate through the remaining elements in the array.
- If the current element is larger than the root of the heap, pop the root and push the current element into the heap.
- Otherwise, continue to the next element.

Pop 3 from the heap and push 6.

Pop 6 from the heap and push 8.

After iterating through all the elements, the heap contains the 3 largest elements in the array.

Solution

import heapq

def three_largest(nums):
    # create a min-heap with the first 3 elements
    heap = nums[:3]
    heapq.heapify(heap)
    
    # iterate through the remaining elements
    for num in nums[3:]:
        if num > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, num)
    
    return heap

Complexity Analysis

Time Complexity:

The heapify function takes O(3) = O(1) time.
We iterate through all the elements in the array once, which takes O(n) time.
The heappop and heappush operations take O(log 3) = O(1) time.

Therefore, the total time complexity is O(n).

Space Complexity

We use a heap of size 3 to store the 3 largest elements, which takes O(3) = O(1) space.
The space complexity of the algorithm is O(1).

The time and space complexity become more interesting when 3 is a variable number, which is the case in the first practice problem.

Next: Kth Largest Element in an Array

Your account is free and you can post anonymously if you choose.

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Binary Search: Search in Rotated Sorted Array

Kth Largest Element in an Array

Heaps

We can think of a heap as an array with a special property: the smallest value in the array is always in the first index of the array.

If we remove the smallest value from the heap, the elements of the array efficiently re-arrange so that the next smallest value takes its place at the front of the array.

Heaps are most frequently used in coding interviews to solve a class of problems known as "Top K" problems, which involve finding the k smallest or largest elements in a collection of elements.

This module prepares you to use heaps during the coding interview by covering:

How heaps are able to achieve their special property efficiently, which enable you to discuss heaps effectively during the interview.
How to use heaps in Python.
The types of coding interview questions that are best solved using heaps.

Heap Properties

Although we can think of a heap as an array, it's more helpful to visualize a heap as a binary tree. For example, we can visualize the heap [1, 2, 4, 5, 8, 6, 9] like this:

The array representation is shown above the heap. Each node in the binary tree is labeled with the corresponding index in the array.

Our heap is a min-heap because the smallest value in the heap is at the root node (compare that to a max-heap, in which the largest value is at the root).

The binary tree satisfies the heap property: each node in the tree has a value that is less than or equal to the values of both its children.

Node 2 has a value that is less than both its children (5 and 8).

Any binary tree that satisfies the heap property is a heap:

Left: A valid heap, right: an invalid heap.

Heaps are complete binary trees, which means that all levels of the tree are fully filled except for the last level, which is filled from left to right.

Left: A valid heap, right: an invalid heap.

Max Heap

The heap property for a max heap is that each node has a value that is greater than or equal to the values of both its children.

Parent-Child Relationship

We can express the parent-child relationships of the binary tree representation of a heap using the indexes of the array. Given a node at index i in the array:

Node	Index
Left Child	2 * i + 1
Right Child	2 * i + 2
Parent	⌊(i - 1) / 2⌋ (floor division)

For example, for the node at index i = 2:

The left child is at index 2 * 2 + 1 = 5:
The right child is at index 2 * 2 + 2 = 6:
The parent is at index ⌊(2 - 1) / 2⌋ = 0:

Heap Operations

A heap supports the following operations:

push(element): Add a new element to the heap.
pop(): Remove the root element from the heap.
peek(): Get the root element without removing it.
heapify([elements]): Convert an array into a heap in-place.