Heaps Interview Questions & Tips for Senior Engineers
Heap Interview Questions & Tips
By Mike Mroczka | Last updated: July 24, 2023
What Is a Heap?
A heap is a special kind of tree-based data structure that satisfies the heap property. In a max heap, for any given node 'i', the value of 'i' is greater than or equal to the values of its children. In a min heap, the value of 'i' is less than or equal to the values of its children.
An interesting aspect of heaps is their shape: they're always complete or almost complete binary trees – by complete, we mean "not missing any children." This characteristic allows us to represent heaps in a compact manner using arrays.
Companies That Ask Heaps Questions
Amazon Interview process & questions Watch 33 interview replays
Microsoft Interview process & questions Watch 24 interview replays
Heap Representation - Arrays!
A heap represented as an array follows this simple rule: if a parent node is at index i, then its left child is at index 2i+1 and the right child is at index 2i+2. Similarly, for a given child node at index i, its parent node is at index (i-1)/2. This calculation is specific to 0-based arrays and is a common one among several variations.
Let's take an example. Suppose we have a max heap as follows:
5
/ \
4 8
/ \ / \
9 7 10 9
/ \ /
15 20 13
This heap can be represented as an array like this:
[5, 4, 8, 9, 7, 10, 9, 15, 20, 13]
A full side by side is shown below for convenience of understanding:
So, if you see the first element of the array which is 5 (index 0), its left child is 4 which we get by calculating (0*2)+1=1 and the right child is 8 which we get by calculating (0*2)+2=2. This pattern continues for the rest of the array, maintaining the heap structure.
Are Heaps Included in Your Language?
Python
Here's a simple way to create a heap in Python using the heapq module:
Python
import heapq
# Min Heap
min_heap = [13, 9, 8, 9, 20, 10, 4, 15, 7, 5]
heapq.heapify(min_heap) # [5, 4, 8, 9, 7, 10, 9, 15, 20, 13]
# Add to heap
heapq.heappush(min_heap, 30) # [5, 7, 8, 9, 9, 10, 4, 15, 20, 13, 30]
# Remove from heap
heapq.heappop(min_heap) # [7, 9, 8, 9, 13, 10, 4, 15, 20, 30]
A fun fact about Python's heapq module is that it only supports a min heap officially. This is because you can get a max heap using the same module by multiplying the contents of each inserted element by -1 to achieve this.
Java
Java provides a built-in PriorityQueue class which is essentially a min heap. For a max heap, you can modify the comparator during the PriorityQueue class instantiation.
Here's an example of creating a min heap and a max heap in Java:
Java
// Min Heap
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
// Max Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
Inserting and deleting elements can be performed using methods such as add(), poll(), and peek().
C++
C++ provides a built-in priority_queue class in the queue library for creating a max heap. To create a min heap, you have to use a greater comparator.
Here's an example:
C++
// Max Heap
priority_queue<int> maxHeap;
// Min Heap
priority_queue<int, vector<int>, greater<int>> minHeap;
The push(), pop(), and top() methods are used to insert, delete, and find the max/min element.
JavaScript
JavaScript does not have a built-in heap data structure. You can mimic a heap using an array and manually maintaining the heap property, but this can be complex. Here is a simple example of how to create a min heap in JavaScript:
JavaScript
class MinHeap {
constructor() {
this.heap = [];
}
// Insert
insert(val) {
this.heap.push(val);
this.bubbleUp();
}
// Bubble Up
bubbleUp() {
let index = this.heap.length - 1;
while (index > 0) {
let element = this.heap[index];
let parentIndex = Math.floor((index - 1) / 2);
let parent = this.heap[parentIndex];
if (parent >= element) break;
this.heap[index] = parent;
this.heap[parentIndex] = element;
index = parentIndex;
}
}
}
Remember, due to JavaScript's lack of a built-in heap structure, it is beneficial for JavaScript developers to familiarize themselves with the fundamental behaviors of heaps to apply similar logic in JavaScript.
Heapify Method Details
Heapify is an essential operation used to maintain the heap property. It's a process of building a heap from an array.
Here is a simple implementation of the heapify function:
def heapify(arr, n, i):
largest = i # Initialize largest as root
l = 2 * i + 1 # left child
r = 2 * i + 2 # right child
# check if left child exists and is greater than root
if l < n and arr[i] < arr[l]:
largest = l
# check if right child exists and is greater than root
if r < n and arr[largest] < arr[r]:
largest = r
# change root if needed
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # swap
# Heapify the root again.
heapify(arr, n, largest)
The heapify operation works by identifying the largest (in case of a max heap) among the root, left child and right child, and swapping it with the root. The time complexity of heapify is O(log n) because we're traversing a tree of height log n.
Heap Time Complexities
Heap complexities are part of what make this data structure worthwhile!
| Operation | Description | Time Complexity |
|---|---|---|
| Build Heap (Heapify all elements) | Construct a heap from an array | O(n) |
| Heapify | Restore heap property by sifting down from a node | O(log n) |
| Insertion | Add a new element to the heap and sift it up | O(log n) |
| Deletion | Remove the root and sift up the last element | O(log n) |
| Peek | Access the root element (max or min) | O(1) |
| Search | Find a specific element in the heap | O(n) |
When to Use Heaps in Interviews
Heaps are particularly useful in scenarios where you have to maintain a 'running maximum' or 'minimum' or when asked to extract the maximum or minimum elements frequently. Some scenarios include:
- Implementing a priority queue
- Finding the 'k' largest or smallest elements in an array
- Sorting an array (HeapSort)
- Median finding problems
Common Mistakes in Interviews Featuring Heaps
While working with heaps, interviewees often make mistakes such as:
- Not choosing the right type of heap: Heaps can be max-heaps or min-heaps. Make sure to choose the correct type.
- Incorrectly indexing children and parents: Remember the formula to find the parent and child nodes.
- Not maintaining heap property while inserting/deleting: Ensure to 'heapify' the heap again afterward.
- Ignoring heap's time complexity: Keep in mind that heap operations are
O(log n)and building a heap isO(n).
What to Say in Interviews to Show Mastery Over Heaps
- Discuss the internal workings of heap operations such as insertion and deletion.
- Talk about how the choice of a heap affects the solution.
- Discuss the efficiency of heap operations in certain problems.
Heap Frequently Asked Questions (FAQs)
Why Are Heaps Preferred Over BST for Priority Queue?
Heaps are preferred because they provide constant time retrieval and logarithmic time insertion and deletion, which makes it a better choice for a priority queue.
What Is the Difference Between a Heap and a Priority Queue?
A priority queue is an abstract concept that defines the behavior and operations of a collection of elements with priorities, while a heap is a specific implementation of a priority queue that satisfies the heap property.
Are Heaps Always Sorted?
No, heaps are not necessarily sorted, but parent nodes will always be less than (min heap) or greater than (max heap) their child nodes.
How Can Heaps Be Used in Sorting?
Heaps can be used to create a sorting algorithm known as HeapSort, which works by organizing the data into a max heap and removing the max element iteratively.
Common Heaps interview Questions
MEDIUM
Data Structures and Algorithms