How Do You Implement a Heap Using an Array
💡 Concept Name
Heap using Array – A binary heap is efficiently represented as an array by leveraging the predictable parent-child index relationships inherent in a complete binary tree.
📘 Quick Intro
A heap is a complete binary tree where every node satisfies the heap property (either min-heap or max-heap). Due to its completeness, the heap nodes can be stored sequentially in an array without using explicit pointers.
🧠 Analogy / Short Story
Imagine stacking oranges in a pyramid inside a flat crate row by row. You don't need strings to connect them; their position in the crate tells you exactly where each orange sits in relation to others. This is how heaps can be stored in arrays.
🔧 Technical Explanation
-
👨👧👦 For a node at index
iin the array:- Left child index =
2 * i + 1 - Right child index =
2 * i + 2 - Parent index =
(i - 1) / 2(integer division)
- Left child index =
- 🏗️ Insertion: Add the new element at the end and bubble it up to maintain the heap property (heapify up).
- ❌ Removal: Remove the root by replacing it with the last element, then heapify down to restore order.
- 📦 Arrays provide a compact and efficient storage model without pointers, leveraging simple index arithmetic.
🎯 Purpose & Use Case
- ✅ Implementing priority queues efficiently
- ✅ Scheduling tasks based on priority
- ✅ In-place sorting algorithms such as heapsort
- ✅ Calculating running medians or maintaining k-largest elements dynamically
💻 Real Code Example
public class MaxHeap
{
private List<int> heap = new List<int>();
public void Insert(int value)
{
heap.Add(value);
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 ExtractMax()
{
if (heap.Count == 0) throw new InvalidOperationException("Heap is empty.");
int max = heap[0];
heap[0] = heap[^1];
heap.RemoveAt(heap.Count - 1);
Heapify(0);
return max;
}
private void Heapify(int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < heap.Count && heap[left] > heap[largest]) largest = left;
if (right < heap.Count && heap[right] > heap[largest]) largest = right;
if (largest != i)
{
(heap[i], heap[largest]) = (heap[largest], heap[i]);
Heapify(largest);
}
}
}
❓ Interview Q&A
Q1: How is a heap represented using an array?
A: The heap elements are stored sequentially in an array, where the parent-child relationship is determined by index calculations.
Q2: How do you find the parent of a node at index i?
A: Parent index = (i - 1) / 2 (integer division).
Q3: How do you find the left child of a node at index i?
A: Left child index = 2 * i + 1.
Q4: How do you find the right child of a node at index i?
A: Right child index = 2 * i + 2.
Q5: Why use an array to represent a heap instead of pointers?
A: Arrays offer cache-friendly memory layout and simple index calculations, improving performance.
Q6: What is the advantage of storing heaps in arrays?
A: No need for explicit pointers; parent and child relationships are implicit via indices.
Q7: How is insertion handled in an array-based heap?
A: Insert the new element at the end and heapify-up to maintain heap property.
Q8: How is removal of the root handled in an array-based heap?
A: Replace root with last element, reduce heap size, and heapify-down.
Q9: What is the time complexity of heap operations using arrays?
A: O(log n) for insertion and deletion.
Q10: Can heaps using arrays be easily resized?
A: Yes, dynamic arrays or array resizing techniques can be applied.
📝 MCQs
Q1. How do you find the parent index in an array-based heap?
- (i - 1) / 2
- 2 * i + 1
- 2 * i + 2
- i / 2
Q2. What is the left child index in an array heap?
- 2 * i + 1
- (i - 1) / 2
- 2 * i + 2
- i - 1
Q3. What is the right child index in an array heap?
- 2 * i + 2
- 2 * i + 1
- (i - 1) / 2
- i + 1
Q4. Why are heaps stored in arrays?
- Easier to program
- Cache-friendly and simple index math
- Faster insertions
- Memory efficient
Q5. How is insertion done in array-based heaps?
- Insert at root
- Insert at end and heapify-up
- Insert randomly
- Insert at middle
Q6. How is root removal done in array-based heaps?
- Delete root directly
- Replace root with last element and heapify-down
- Swap root with left child
- Remove last element
Q7. What is the time complexity of insertion and removal in heaps?
- O(1)
- O(n)
- O(log n)
- O(n log n)
Q8. Can array-based heaps be resized?
- No
- Yes, using dynamic arrays
- Only fixed size
- Depends on implementation
Q9. What does heapify do?
- Sorts the array
- Maintains heap property after changes
- Deletes nodes
- Adds nodes
Q10. What property does a max-heap maintain?
- Parent <= children
- Parent >= children
- Children unordered
- No order
💡 Bonus Insight
Storing heaps in arrays reduces memory overhead and enables efficient in-place sorting through heapsort, which runs in O(n log n) time with minimal extra space.
📄 PDF Download
Need a handy summary for your notes? Download this topic as a PDF!