What is a Min-Heap and Max-Heap?
💡 Concept Name
Min-Heap and Max-Heap – Specialized binary trees used in priority queue implementations. A min-heap keeps the smallest element at the root, whereas a max-heap keeps the largest at the root.
📘 Quick Intro
Heaps are complete binary trees satisfying the heap property: in a min-heap, parents are always less than or equal to their children; in a max-heap, parents are greater than or equal. They enable fast priority-based operations and are used in algorithms like Dijkstra’s.
🧠 Analogy / Short Story
Imagine a leaderboard: a min-heap is like always seeing the player with the lowest score on top, while a max-heap shows the highest scorer first. This makes it easy to quickly find the smallest or largest values.
🔧 Technical Explanation
- 🧱 Min-Heap: The root node holds the smallest value; child nodes are greater or equal.
- 🧱 Max-Heap: The root node holds the largest value; child nodes are smaller or equal.
- 🔄 Insertion: Add the new element at the end and "bubble up" to restore heap order.
- ❌ Deletion: Remove the root, replace it with the last element, then "bubble down" to fix the heap.
- ⏱️ Complexity: Insert and delete operations run in O(log n) time, while peeking at the root is O(1).
🎯 Purpose & Use Case
- ✅ Implementing efficient priority queues.
- ✅ Task scheduling and resource management.
- ✅ Graph algorithms like Dijkstra’s and Prim’s MST.
- ✅ Performing heap sort.
💻 Real Code Example
public class MinHeap
{
private List<int> heap = new List<int>();
public void Insert(int val)
{
heap.Add(val);
int i = heap.Count - 1;
while (i > 0 && heap[i] < heap[(i - 1) / 2])
{
(heap[i], heap[(i - 1) / 2]) = (heap[(i - 1) / 2], heap[i]);
i = (i - 1) / 2;
}
}
public int PeekMin() => heap.Count > 0 ? heap[0] : throw new InvalidOperationException();
}
❓ Interview Q&A
Q1: What is a min heap?
A: A binary heap where the parent node is smaller than or equal to its children, so the smallest element is at the root.
Q2: What is a max heap?
A: A binary heap where the parent node is greater than or equal to its children, so the largest element is at the root.
Q3: Where is the smallest element located in a min heap?
A: At the root node.
Q4: Where is the largest element located in a max heap?
A: At the root node.
Q5: How are min heaps and max heaps typically represented?
A: As binary trees stored in arrays.
Q6: What is the time complexity of insertion in both heaps?
A: O(log n) due to heapify operations.
Q7: What is the key difference between min heap and max heap?
A: Min heap keeps minimum at root; max heap keeps maximum at root.
Q8: Can min heaps be used to implement priority queues?
A: Yes, for extracting minimum priority elements efficiently.
Q9: Can max heaps be used for sorting algorithms?
A: Yes, heap sort commonly uses max heaps.
Q10: How do heapify-up and heapify-down operations maintain heap property?
A: By swapping nodes up or down to restore order after insertions or deletions.
📝 MCQs
Q1. What property does a min heap maintain?
- Parent >= children
- Parent <= children
- Parent = children
- No order
Q2. What property does a max heap maintain?
- Parent <= children
- Parent >= children
- Children are unordered
- Heap is sorted
Q3. Where is the smallest element in a min heap?
- At the leaf
- At the root
- Random
- At the middle
Q4. Where is the largest element in a max heap?
- At the leaf
- At the root
- Random
- At the middle
Q5. What is the typical time complexity to insert in a heap?
- O(1)
- O(n)
- O(log n)
- O(n log n)
Q6. What data structure usually represents heaps?
- Linked list
- Array-based binary tree
- Hash table
- Graph
Q7. Which heap is used to implement a min-priority queue?
- Max heap
- Min heap
- Binary search tree
- AVL tree
Q8. Which heap is typically used in heap sort?
- Min heap
- Max heap
- Trie
- Graph
Q9. What operation restores heap property after insertion?
- Heapify-down
- Heapify-up
- Sort
- Balance
Q10. What operation restores heap property after deletion?
- Heapify-up
- Heapify-down
- Sort
- Balance
💡 Bonus Insight
Heaps are typically implemented as arrays where the parent-child relationship can be calculated by indices: for parent at index i, children are at 2i+1 and 2i+2.
📄 PDF Download
Need a handy summary for your notes? Download this topic as a PDF!