Heap Concept Structure and Properties in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Max-Heap after Insertions

What is the printed state of the max-heap array after inserting the elements 10, 20, 5, 30 in this order?

DSA C++

std::vector<int> heap;

void heapifyUp(std::vector<int>& heap, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap[parent] < heap[index]) {
            std::swap(heap[parent], heap[index]);
            index = parent;
        } else {
            break;
        }
    }
}

void insert(std::vector<int>& heap, int val) {
    heap.push_back(val);
    heapifyUp(heap, heap.size() - 1);
}

int main() {
    insert(heap, 10);
    insert(heap, 20);
    insert(heap, 5);
    insert(heap, 30);
    for (int val : heap) {
        std::cout << val << " ";
    }
    return 0;
}

A [20, 30, 10, 5]

B [10, 20, 5, 30]

C [5, 10, 20, 30]

D [30, 20, 5, 10]

💡 Hint

Remember max-heap property: parent is always greater than children.

After inserting 10, heap is [10]. Insert 20, heapify up swaps 20 and 10 → [20, 10]. Insert 5, no swap → [20, 10, 5]. Insert 30, heapify up swaps 30 with 10, then with 20 → [30, 20, 5, 10].

🧠 Conceptual

intermediate

Heap Property Identification

Which of the following arrays represents a valid min-heap?

A [3, 5, 8, 10, 15, 9]

B [3, 10, 5, 8, 15, 9]

C [5, 3, 8, 10, 15, 9]

D [10, 15, 9, 3, 5, 8]

💡 Hint

In a min-heap, every parent node is less than or equal to its children.

Option A satisfies min-heap property: 3 ≤ 5 and 8, 5 ≤ 10 and 15, 8 ≤ 9. Others violate this property.

🔧 Debug

advanced

Identify the Error in Heapify Down Function

What error will occur when running this heapifyDown function on a max-heap?

DSA C++

void heapifyDown(std::vector<int>& heap, int index) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int largest = index;

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

    if (largest != index) {
        std::swap(heap[index], heap[largest]);
        heapifyDown(heap, largest);
    }
}

A Stack overflow due to infinite recursion

B No error, function works correctly

C Out of range error accessing heap vector

D Compilation error due to missing return statement

💡 Hint

Check the base case and recursive calls carefully.

The function correctly checks bounds and swaps only when needed, then recurses on the child. No infinite recursion or out-of-range access occurs.

❓ Predict Output

advanced

Heap Array After Extracting Max

Given a max-heap represented by array [40, 30, 35, 15, 10, 25], what is the heap array after extracting the max element once?

DSA C++

std::vector<int> heap = {40, 30, 35, 15, 10, 25};

void heapifyDown(std::vector<int>& heap, int index) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int largest = index;

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

    if (largest != index) {
        std::swap(heap[index], heap[largest]);
        heapifyDown(heap, largest);
    }
}

void extractMax(std::vector<int>& heap) {
    heap[0] = heap.back();
    heap.pop_back();
    heapifyDown(heap, 0);
}

int main() {
    extractMax(heap);
    for (int val : heap) {
        std::cout << val << " ";
    }
    return 0;
}

A [25, 30, 35, 15, 10]

B [30, 25, 35, 15, 10]

C [35, 30, 25, 15, 10]

D [35, 30, 10, 15, 25]

💡 Hint

After removing max, replace root with last element and heapify down.

Replace 40 with 25 → [25, 30, 35, 15, 10]. Heapify down swaps 25 with 35 → [35, 30, 25, 15, 10].

🧠 Conceptual

expert

Height of a Complete Binary Heap with N Nodes

What is the height of a complete binary heap with 1000 nodes?

A 9

B 12

C 11

D 10

💡 Hint

Height is floor of log base 2 of number of nodes.

Height h = floor(log2(1000)) ≈ 9.96, floor is 9.