Heap Concept Structure and Properties in DSA C#

Mental Model

A heap is a special tree where each parent is bigger (max-heap) or smaller (min-heap) than its children, making it easy to find the biggest or smallest item quickly.

Analogy: Imagine a family tree where parents are always taller than their children, so the tallest person is always at the top, making it easy to spot the tallest family member.

       10
      /  \
     5    3
    / \  / \
   2  4 1 null

Dry Run Walkthrough

Input: Build a max-heap from array [2, 5, 3, 10, 4, 1]

Goal: Arrange the array elements into a max-heap where each parent is greater than its children

Step 1: Start from the last parent node (index 2 with value 3) and heapify

Array: [2, 5, 3, 10, 4, 1]
Heap:
       2
      /  \
     5    3
    / \   /
   10  4 1

Why: We fix the subtree rooted at index 2 to satisfy max-heap property

Step 2: Move to parent node at index 1 (value 5) and heapify

Array: [2, 10, 3, 5, 4, 1]
Heap:
       2
      /  \
    10    3
    / \   /
    5  4 1

Why: Swap 5 with 10 to maintain max-heap property at this subtree

Step 3: Move to root node at index 0 (value 2) and heapify

Array: [10, 5, 3, 2, 4, 1]
Heap:
      10
      /  \
     5    3
    / \   /
   2  4 1

Why: Swap 2 with 10 and then 2 with 5 to fix max-heap property at root

Result:

Final max-heap array: [10, 5, 3, 2, 4, 1]
Heap:
      10
      /  \
     5    3
    / \   /
   2  4 1

Annotated Code

DSA C#

using System;

class MaxHeap
{
    private int[] heap;
    private int size;

    public MaxHeap(int[] array)
    {
        heap = array;
        size = array.Length;
        BuildMaxHeap();
    }

    private void BuildMaxHeap()
    {
        for (int i = size / 2 - 1; i >= 0; i--)
        {
            Heapify(i);
        }
    }

    private void Heapify(int i)
    {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < size && heap[left] > heap[largest])
            largest = left; // find larger child on left

        if (right < size && heap[right] > heap[largest])
            largest = right; // find larger child on right

        if (largest != i)
        {
            int temp = heap[i];
            heap[i] = heap[largest];
            heap[largest] = temp; // swap parent with largest child

            Heapify(largest); // recursively heapify affected subtree
        }
    }

    public void PrintHeap()
    {
        for (int i = 0; i < size; i++)
            Console.Write(heap[i] + (i == size - 1 ? "\n" : ", "));
    }
}

class Program
{
    static void Main()
    {
        int[] array = { 2, 5, 3, 10, 4, 1 };
        MaxHeap maxHeap = new MaxHeap(array);
        maxHeap.PrintHeap();
    }
}

for (int i = size / 2 - 1; i >= 0; i--)

start heapify from last parent node moving up to root

Heapify(i);

fix subtree rooted at i to maintain max-heap property

if (left < size && heap[left] > heap[largest]) largest = left;

check if left child is larger than current largest

if (right < size && heap[right] > heap[largest]) largest = right;

check if right child is larger than current largest

if (largest != i) { swap and Heapify(largest); }

swap parent with largest child and heapify affected subtree

Output

10, 5, 3, 2, 4, 1

Complexity Analysis

Time: O(n) because building a heap requires heapifying all non-leaf nodes once

Space: O(1) because heap is built in place without extra storage

vs Alternative: Compared to sorting first then building heap, this method is faster and more efficient

Edge Cases

Empty array

No heap is built, no errors occur

DSA C#

for (int i = size / 2 - 1; i >= 0; i--)

Single element array

Heap is the single element itself, no swaps needed

DSA C#

for (int i = size / 2 - 1; i >= 0; i--)

All elements equal

Heap property holds trivially, no swaps needed

DSA C#

if (largest != i)

When to Use This Pattern

When you need quick access to the largest or smallest element repeatedly, recognize the heap pattern because it keeps the biggest or smallest item at the top efficiently.

Common Mistakes

Mistake: Starting heapify from the root instead of last parent node
Fix: Start heapify from last parent node (size/2 - 1) moving upwards

Mistake: Not recursively heapifying after a swap
Fix: Call Heapify recursively on the swapped child's index to fix subtree

Summary

A heap is a tree structure where parents are always bigger (max-heap) or smaller (min-heap) than children.

Use a heap when you want fast access to the largest or smallest item in a collection.

The key is to fix the heap property from the bottom up by heapifying subtrees starting at the last parent.

Practice

1. What is a key property of a max-heap data structure?

easy

A. Every parent node is greater than or equal to its children

B. Every parent node is less than or equal to its children

C. All leaf nodes have the same value

D. The tree is always a complete binary tree with sorted leaves

Solution

1. Step 1: Understand max-heap property

   A max-heap requires that each parent node's value is greater than or equal to the values of its children.

2. Step 2: Compare options with definition

   Every parent node is greater than or equal to its children matches the max-heap property exactly. Every parent node is less than or equal to its children describes a min-heap. Options A and C are incorrect properties.

3. Final Answer:

   Every parent node is greater than or equal to its children -> Option A

4. Quick Check:

   Max-heap = parent ≥ children [OK]

Hint: Max-heap means parent ≥ children values [OK]

Common Mistakes:

• Confusing max-heap with min-heap property
• Thinking leaves must be sorted
• Assuming all nodes have equal values

2. Which of the following is the correct way to declare a min-heap using C#'s PriorityQueue?

easy

A. var minHeap = new PriorityQueue();

B. var minHeap = new PriorityQueue(Comparer<int>.Default);

C. var minHeap = new PriorityQueue(Comparer<int>.Create((x, y) => y - x));

D. var minHeap = new PriorityQueue(Comparer<int>.Create((x, y) => x + y));

Solution

1. Step 1: Recall default behavior of PriorityQueue

   In C#, PriorityQueue by default acts as a min-heap using the natural order of TPriority.

2. Step 2: Analyze options

   var minHeap = new PriorityQueue(); uses default constructor, creating a min-heap. var minHeap = new PriorityQueue(Comparer<int>.Default); incorrectly tries to pass a comparer to constructor which does not exist. var minHeap = new PriorityQueue(Comparer<int>.Create((x, y) => y - x)); reverses order for max-heap. var minHeap = new PriorityQueue(Comparer<int>.Create((x, y) => x + y)); uses invalid comparer logic.

3. Final Answer:

   var minHeap = new PriorityQueue<int, int>(); -> Option A

4. Quick Check:

   Default PriorityQueue is min-heap [OK]

Hint: Default PriorityQueue is min-heap without comparer [OK]

Common Mistakes:

• Trying to pass comparer to constructor (not supported)
• Using wrong comparer logic for min-heap
• Confusing min-heap and max-heap syntax

3. Consider the following C# code using a max-heap implemented as a binary heap array:

int[] heap = { 50, 30, 40, 10, 20 };
// Insert 60 and then heapify up
Insert(heap, 60);

What will be the heap array after insertion?

medium

A. [60, 50, 40, 10, 20, 60]

B. [60, 30, 50, 10, 20, 40]

C. [60, 50, 40, 30, 20, 10]

D. [50, 30, 40, 10, 20, 60]

Solution

1. Step 1: Insert 60 at the end of heap array

   Initial heap: [50, 30, 40, 10, 20]. Insert 60 at index 5: [50, 30, 40, 10, 20, 60]

2. Step 2: Heapify up to maintain max-heap

   Compare 60 with parent at index 2 (40). 60 > 40, swap. New array: [50, 30, 60, 10, 20, 40]. Compare 60 with parent at index 0 (50). 60 > 50, swap. Final array: [60, 30, 50, 10, 20, 40]

3. Final Answer:

   [60, 30, 50, 10, 20, 40] -> Option B

4. Quick Check:

   Insert + heapify up = [60,30,50,10,20,40] [OK]

Hint: Insert at end, swap up while parent smaller [OK]

Common Mistakes:

• Not swapping with parent correctly
• Placing new element at wrong index
• Confusing heapify up with heapify down

4. The following C# code attempts to remove the root from a max-heap stored in an array but has a bug:

void RemoveRoot(int[] heap, int size) {
    heap[0] = heap[size - 1];
    size--;
    HeapifyDown(heap, 0, size);
}

What is the main issue causing incorrect heap behavior?

medium

A. HeapifyDown is called with wrong starting index

B. The last element is not removed before assignment

C. The size variable is decremented locally but not updated outside

D. The root is not replaced with the maximum child

Solution

1. Step 1: Analyze size decrement scope

   The size variable is decremented inside the method but since it's passed by value, the caller's size remains unchanged.

2. Step 2: Effect on heap operations

   Because size outside is not updated, heap operations may access invalid elements or not reflect the reduced heap size, causing incorrect behavior.

3. Final Answer:

   Size variable is decremented locally but not updated outside -> Option C

4. Quick Check:

   Size must update outside method [OK]

Hint: Pass size by ref or return new size [OK]

Common Mistakes:

• Assuming size changes persist without ref
• Thinking heapify down index is wrong
• Ignoring size update importance

5. You have a min-heap represented as an array: [5, 10, 15, 20, 25, 30]. You want to replace the root with 22 and restore the min-heap property. Which sequence of array states correctly shows the heap after replacing and heapifying down?

hard

A. [22, 10, 15, 20, 25, 30] -> [10, 22, 15, 20, 25, 30]

B. [22, 10, 15, 20, 25, 30] -> [10, 15, 22, 20, 25, 30]

C. [22, 10, 15, 20, 25, 30] -> [15, 10, 22, 20, 25, 30]

D. [22, 10, 15, 20, 25, 30] -> [10, 20, 15, 22, 25, 30]

Solution

1. Step 1: Replace root with 22

   Initial heap: [5, 10, 15, 20, 25, 30]. Replace root 5 with 22: [22, 10, 15, 20, 25, 30]

2. Step 2: Heapify down to restore min-heap

   Compare 22 with children 10 and 15. Smallest child is 10. Swap 22 and 10: [10, 22, 15, 20, 25, 30]. Now 22 at index 1 has children at indices 3 (20) and 4 (25). Smallest is 20 < 22, swap 22 and 20: [10, 20, 15, 22, 25, 30]. 22 now at index 3 has no children, stop.

3. Final Answer:

   [22, 10, 15, 20, 25, 30] -> [10, 20, 15, 22, 25, 30] -> Option D

4. Quick Check:

   Replace root + heapify down = [22,10,15,20,25,30] -> [10,20,15,22,25,30] [OK]

Hint: Swap root down with smallest child until heap restored [OK]

Common Mistakes:

• Swapping with wrong child
• Stopping heapify too early
• Confusing min-heap with max-heap rules