How can you store a heap in an array?

A binary heap can be stored in an array by arranging nodes level-by-level and using index calculations to find parent and child positions.

What is the parent index of node i in a heap array?

The parent index for node i is calculated as (i - 1) / 2.

How Do You Implement a Heap Using an Array | FullStackPrep.Dev

💡 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 i in the array:
- Left child index = 2 * i + 1
- Right child index = 2 * i + 2
- Parent index = (i - 1) / 2 (integer division)
🏗️ 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!

📄 PDF Download Coming Soon

How Do You Implement a Heap Using an Array