50+ heap interview questions and cheat sheet

To ace your interview for a software engineering job, you’ll need to understand heaps. They come up frequently in coding interviews.

Let’s take a look at some typical heap questions.

Below, we take a look at some more questions and provide you with links to high quality solutions to them. We explain how heaps work, their variations, and the most important things you need to know about them, including a useful "cheat sheet" to remind you of the key points at a glance.

This is an overview of what we’ll cover:

1. Easy heap interview questions
2. Medium heap interview questions
3. Hard heap interview questions
4. Heap basics
5. Heaps cheat sheet
6. Mock interviews for software engineers

Click here to practice coding interviews with ex-FAANG interviewers

1. Easy heap interview questions

You might be tempted to try to read all of the possible questions and memorize the solutions, but this is not feasible. Interviewers will always try to find new questions, or ones that are not available online. Instead, you should use these questions to practice the fundamental concepts of heaps.

As you consider each question, try to replicate the conditions you’ll encounter in your interview. Begin by writing your own solution without external resources in a fixed amount of time.

If you get stuck, go ahead and look at the solutions, but then try the next one alone again. Don’t get stuck in a loop of reading as many solutions as possible! We’ve analysed dozens of questions and selected ones that are commonly asked and have clear and high quality answers.

Here are some of the easiest questions you might get asked in a coding interview. These questions are often asked during the "phone screen" stage, so you should be comfortable answering them without being able to write code or use a whiteboard.

2. Medium heap interview questions

Here are some moderate-level questions that are often asked in a video call or onsite interview. You should be prepared to write code or sketch out the solutions on a whiteboard if asked.

3. Hard heap interview questions

Similar to the medium section, these more difficult questions may be asked in an onsite or video call interview. You will likely be given more time if you are expected to create a full solution.

4. Heap basics

In order to crack the questions above and others like them, you’ll need to have a strong understanding of heaps, how they work, and when to use them. Let’s get into it.

4.1 What are heaps?

A heap is a tree-based data structure that implements a priority queue. A priority queue functions much like a regular stack or queue, except that each element has a priority. It is this priority that determines which element is returned when dequeuing from the priority queue, rather than the order in which the element was added. This is useful for applications like a hospital queue where we want to serve the patient with the highest priority first. 

A heap must satisfy the heap property. The heap property states that a node must have a value, or key, greater than or equal to (≥) the value of its child node for a max-heap, and less than or equal to (≤) to the value of its child node for a min-heap. The relative ordering of the child nodes does not matter, i.e. it is not required that the smaller child be on the left or right of the parent node.

4.1.1 Types of heaps (Java, Python, C++)

Java provides the “PriorityQueue” class, which is based on the heap structure. The priority queue relies on “natural order,” making it a min-heap implementation. But passing a custom comparator to the constructor allows you to implement it as a max-heap. All items added to the priority queue class must be comparable, so a null element cannot be added.

Various C++ helper functions allow you to make an iterator operate as a heap. Among them are:

• “make_heap,” which rearranges the elements in an iterator to form a heap; 
• “push_heap,” which adds a new element to a heap and restores the heap property; and
• “pop_heap,” which removes the root element and restores the heap property.

Heaps in C++ are implemented as max-heap by default, but a custom comparator can be used to implement min-heaps. The “priority_queue” container adapter in C++ encapsulates these function calls on any container, like vector or deque containers.

Python has the “heapq” type, which is a min-heap implementation.

4.1.2 How heaps store data

Heaps are usually implemented using an array representation of a binary tree. This requires mapping an almost complete binary tree as an array: the root of the tree is at arr[0], the left child for any parent i is at arr[2i + 1] and the right child at arr[2i + 2], as you can see in the diagram below. Java and Python use arrays for their heap implementations. C++ also uses arrays when using the vector container.

Variants of heap implementations also exist, two of which are binomial heaps and Fibonacci heaps. A binomial heap is a set of binomial trees, while a Fibonacci heap is a set of normal trees. In both variants, the subtrees must satisfy the min-heap property. This means that the root of each tree contains the minimum element for that tree, and the minimum root of all the trees will be the minimum value for the whole collection. The roots of subtrees are stored in a linked list in binomial heaps and in a doubly linked list in Fibonacci heaps, allowing for iteration over the roots. This iteration adds some time complexity, so both implementations also have a direct pointer to the minimal root.

4.1.3 How heaps compare to other data structures

Heaps are a subtype of priority queues, which allow quick access to the element with the highest priority. They are also similar to any sorted list, tree, or array. A sorted list has an insert cost of O(n); a sorted tree takes O(log n) to find the min/max; and a sorted array has a delete of O(n).

Heaps are also similar to stacks and regular queues, since most implementations have push, pop and peek methods. Heaps, however, are specialized for popping the element with the highest priority, instead of the first in, first out (FIFO) rule for queues and last in, first out (LIFO) rule for stacks. 

Need a boost in your career as a software engineer?

If you want to improve your skills as an engineer or leader, tackle an issue at work, get promoted, or understand the next steps to take in your career, book a session with one of our software engineering coaches.

5. Heaps cheat sheet

You can download the cheat sheet here.

5.1 Related algorithms and techniques

• Fibonacci heap

• Leonardo heap

• Binomial heap

• Pairing heap

• Smoothsort

• Heapsort

• Bucket sort

• Huffman Coding 

• Prim’s algorithm

• Online algorithm

• Dijkstra’s algorithm

5.2 Cheat sheet explained

The cheat sheet above is a summary of information you might need to know for an interview, but it’s usually not enough to simply memorize it. Instead, aim to understand each result so that you can give the answer in context.

The cheat sheet is broken into time complexity (the processing time for various heap operations) and algorithm complexity (the amount of time and space used for common algorithms).

For more information about time and space requirements of different algorithms, read our complete guide to big-O notation and complexity analysis.

5.2.1 Time complexity

A peek operation for the minimum element in a min-heap or the maximum element in a max-heap has a constant time, since this value is always at the root of the heap. Pushing an element might need a heapify-up operation all the way to the root, and popping the root might need a heapify-down operation all the way to the leaves. Since an almost complete binary tree has a height of log(n), the worst case for pushing and popping is O(log n).

It is also possible to decrease any value in a min-heap (or increase a value for a max-heap). Changing a value may violate the heap property, meaning a heapify operation is required to restore the heap. Searching a heap means visiting each node until the item is found, leading to a time complexity of O(n).

The binomial and Fibonacci heap variants can have constant time insertions, as these structures create a new heap with the addition of a new element, which is then merged with the current heap. This simply means the roots of the second heap are added to the list of roots for the first heap.

5.2.2 Space complexity

All the implementations will use up O(n) space. All the tree implementations will have only n nodes in the trees and the array implementation, like all arrays, will be some size of n to 2n.

5.2.3 Heap algorithms complexity

If we have a heap with n elements and continually pop the root until the heap is empty, then we will have extracted the items in order, which is the basics of a heapsort. Since popping is O(log n), this sort will be O(n log(n)). But for an already sorted list, popping the root means moving the last element to the root just to heapify-down again, taking O(log n) time. So the best case is also O(n log(n)) time.

Smoothsort improves this best case by borrowing from the idea of a binomial heap – it uses a collection of Leonardo heaps instead. Unlike the binomial heaps, the roots are ordered to give a linear performance for an already sorted list.

An alternative to finding the kth smallest element from a list is quickselect. Like quicksort, it swaps elements around a pivot point iteratively. Unlike quicksort, the iteration only continues for one side of the pivot to give an average case that reduces to O(n). Poorly chosen pivot points can result in a worst case of O(n^2).

Dijkstra’s shortest path algorithm has a step to find the next shortest path from a list of unvisited vertices. Using a priority queue can improve the runtime of this step, and since heaps are a priority queue, they are a perfect match. At this step we will need to pop the root unvisited vertex for a complexity of O(log V).

 

 

6. Mock interviews for software engineers

Before you start practicing interviews, you’ll want to make sure you have a strong understanding of not only heaps but also the rest of the relevant data structures. Check out our guides for questions, explanations and helpful cheat sheets.

• Arrays
• Strings
• Linked lists
• Stacks and Queues
• Trees
• Graphs
• Maps
• Coding interview examples (with solutions)

Once you’re confident on all the topics, you’ll want to start practicing answering coding questions in an interview situation. One way of doing this is by practicing out loud, which is a very underrated way of preparing. However, sooner or later you’re probably going to want some expert interventions and feedback to really improve your interview skills.

That’s why we recommend practicing with ex-interviewers from top tech companies. If you know a software engineer who has experience running interviews at a big tech company, then that's fantastic. But for most of us, it's tough to find the right connections to make this happen. And it might also be difficult to practice multiple hours with that person unless you know them really well.

Here's the good news. We've already made the connections for you. We’ve created a coaching service where you can practice 1-on-1 with ex-interviewers from leading tech companies. Learn more and start scheduling sessions today.