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.
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. It isn't important to know multiple implementations, just to know a specific one for interviews.
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?
Some languages provide support for heaps in additional modules or libraries. Each language is unique and has its own nuances to heaps. Study the sections below to see how heaps differ between core languages.
Python
Here's a simple way to create a heap in Python using the heapq module:
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.heappush(min_heap) # [7, 9, 8, 9, 13, 10, 4, 15, 20, 30]
1import heapq
2
3# Min Heap
4min_heap = [13, 9, 8, 9, 20, 10, 4, 15, 7, 5]
5heapq.heapify(min_heap) # [5, 4, 8, 9, 7, 10, 9, 15, 20, 13]
6
7# Add to heap
8heapq.heappush(min_heap, 30) # [5, 7, 8, 9, 9, 10, 4, 15, 20, 13, 30]
9
10# Remove from heap
11heapq.heappush(min_heap) # [7, 9, 8, 9, 13, 10, 4, 15, 20, 30]
12A 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 effectively makes the largest elements now the smallest and vice versa. See more details here
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:
// Min Heap
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
// Max Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
1// Min Heap
2PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
3
4// Max Heap
5PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
6Inserting and deleting elements, finding the min/max element can all be performed using inbuilt methods such as add(), poll(), and peek().
C++
C++ also provides a built-in priority_queue class in the queue library for creating max heap. To create a min heap, you have to use a greater comparator.
Here's an example:
// Max Heap
priority_queue<int> maxHeap;
// Min Heap
priority_queue<int, vector<int>, greater<int> > minHeap;
1// Max Heap
2priority_queue<int> maxHeap;
3
4// Min Heap
5priority_queue<int, vector<int>, greater<int> > minHeap;
6The push(), pop(), and top() methods are used to insert, delete, and find the max/min element.
JavaScript
Unfortunately for JavaScript developers, there is not a built-in heap data structure in our language. However, this doesn't mean that we can't solve heap-related problems in JavaScript. We have two options here:
- We can mimic a heap using an array and manually maintaining the heap property, though this can be a bit complex and is time consuming in interviews.
- We can create the heap methods once on our own during practice to understand how they work, but then in an actual interview we would simply pretend we have the implementation built already. To be clear, by "pretend" we don't mean to try and pull one over on your interviewer, feel free to let them know that JavaScript doesn't have a built-in data structure for heaps and you're just going to mock the interview as if it does. When stated confidently most interviewers will not ask you to actually build an entire heap from scratch, "JavaScript doesn't have heaps built in by default, so I'll just mock calling an API for now to save time."
Creating a heap isn't particularly difficult in JavaScript, but again, it can be time consuming. Here is a simple example of how to create a min heap in 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;
}
}
// ... (additional methods like remove, heapify can be implemented similarly)
}
1class MinHeap {
2 constructor() {
3 this.heap = [];
4 }
5
6 // Insert
7 insert(val) {
8 this.heap.push(val);
9 this.bubbleUp();
10 }
11
12 // Bubble Up
13 bubbleUp() {
14 let index = this.heap.length - 1;
15 while (index > 0) {
16 let element = this.heap[index];
17 let parentIndex = Math.floor((index - 1) / 2);
18 let parent = this.heap[parentIndex];
19
20 if (parent >= element) break;
21 this.heap[index] = parent;
22 this.heap[parentIndex] = element;
23 index = parentIndex;
24 }
25 }
26
27 // ... (additional methods like remove, heapify can be implemented similarly)
28}
29Remember, due to JavaScript's lack of a built-in heap structure, it is beneficial for JavaScript developers to familiarize themselves with Python's heapq module, to understand the heap data structure's fundamental behaviors and methods. This understanding can then be translated into JavaScript by creating a custom heap class or object as shown above.
By translating the basic concepts of heaps into various programming languages, you can further enhance your understanding of this versatile data structure and become better prepared for any heap-related questions you might encounter in technical interviews.
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. It ensures that the parent node is always maintaining the heap property with respect to its children.
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)
1def heapify(arr, n, i):
2 largest = i # Initialize largest as root
3 l = 2 * i + 1 # left child
4 r = 2 * i + 2 # right child
5
6 # check if left child exists and is greater than root
7 if l < n and arr[i] < arr[l]:
8 largest = l
9
10 # check if right child exists and is greater than root
11 if r < n and arr[largest] < arr[r]:
12 largest = r
13
14 # change root if needed
15 if largest != i:
16 arr[i], arr[largest] = arr[largest], arr[i] # swap
17
18 # Heapify the root again.
19 heapify(arr, n, largest)
20The 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. Then, it recursively calls the heapify method on the affected subtree. The time complexity of the heapify method is O(log n) because we're essentially traversing a tree of height log n.
Heap Time Complexities
Heap complexities are part of what make this data structure so worthwhile! Be sure to understand the complexities of each operation below.
| 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)` |
A common misconception is the time complexity of heapifying all elements. If you have N elements and you need to add them all to the heap and we know that inserting a single element takes O(log N) time, it is natural to assume heapifying an entire array would take O(N log N) time. This, however, is not true. We can heapify a full array in just O(N), because we would use the heapify method to process the elements.
When to Use Heaps in Interviews
Heaps are particularly useful in scenarios where you have to maintain a 'running maximum' or 'minimum' or when you're asked to extract the maximum or minimum elements frequently. Some scenarios where heaps are useful include:
- Implementing a priority queue
- Finding the 'k' largest or smallest elements in an array
- Sorting an array (HeapSort)
- Median finding problems
See a list of common heap questions below
The power of a heap lies in its efficiency. Operations like insertion, deletion, and retrieval of the maximum/minimum element can be done in O(log n) time. Oftentimes you'll see them crop up as optimal solutions for problems that typically can only be done in O(n log n) and with the heap can be solved in either O(k log n) or O(n log k) time by restricting the size of your heap.
Common Mistakes in Interviews Featuring Heaps
While working with heaps, interviewees often make the following mistakes:
- Not choosing the right type of heap: Heaps can be max-heaps or min-heaps. Make sure to choose the correct type for your problem.
- Incorrectly indexing children and parents: In a heap represented as an array, remember the formula to find the parent and child nodes. If
iis a parent,2i+1and2i+2are its children. Ifiis a child,(i-1)/2(integer division) is its parent. - Not maintaining heap property while inserting/deleting: When you insert or delete an element, make sure to 'heapify' the heap again to maintain the heap property.
- Ignoring heap's time complexity: Although heaps offer efficient operations, keep in mind the time complexity. Heap operations are
O(log n), and building a heap isO(n).
What to Say in Interviews to Show Mastery Over Heaps
Here are a few things you can mention in your interviews to demonstrate your understanding of heaps:
- Discuss the internal working of heap operations, such as insertion, deletion, and heapify.
- Talk about how the choice of a heap (min-heap or max-heap) affects the solution.
- Discuss the efficiency of heap operations and how they provide an edge over other data structures in certain problems.
- Mention how heaps can be used in a variety of problems, like sorting, finding kth smallest/largest elements, implementing a priority queue, etc.
- Talk about how heaps are represented in memory as arrays for efficient use of space.
Heap Frequently Asked Questions (FAQs)
Why Are Heaps Preferred Over BST for Priority Queue?
Heaps are preferred because they offer 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. Stated differently, heaps are priority queues, but not all priority queues are heaps.
Are Heaps Always Sorted?
No, while the parent nodes will always be less than or greater than their child nodes in a min heap and max heap respectively, this doesn't mean the data structure is sorted.
What Is a Heap Overflow?
A heap overflow can occur when we try to insert an element into a heap that's already full.
How Can Heaps Be Used in Sorting?
Heaps can be used to create a sorting algorithm known as HeapSort. This algorithm works by first organizing the data into a max heap, and then swapping the top element (the max) with the last element, decreasing the heap size by one, and finally heapifying the root again. Repeat these steps until the heap size is one, and voila, your array is sorted!
Remember, understanding heaps requires both theoretical knowledge and practical experience. Try to implement heaps from scratch and solve various heap-based problems to get a thorough understanding of the concept.
K Closest Points To Origin
Given a list of tuples that represent (X, Y) coordinates on an XY plane and an integer K, return a list of the K-closest points to the origin (0, 0).
Top K Frequent Elements
Given a non-empty array of integers, return the k most frequent elements.
Build a Max Heap From an Array
Given an array of integers, transform the array in-place to a max heap.
Meeting Rooms
Given a list of meetings, represented as tuples with a start and an end time, determine the minimum number of rooms required to schedule all the meetings.
K Largest Elements
Write an efficient program for printing k largest elements in an array. Largest elements are returned in order largest to smallest.
About the Author
The Mighty Anomaly (Mike) is one of the top Google coaches for interviewing.io having personally helped over 100+ engineers get into Google with his unique coaching style. After receiving offers from the full FAANG gauntlet early in his career, he enjoys teaching others proven techniques to pass technical interviews with his decade of coaching and industry experience.
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
