Why Heap Exists and What Sorted Array Cannot Do Efficiently in DSA C++ - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a new element into a max heap.

DSA C++

void insert(int heap[], int& size, int value) {
    size++;
    heap[size] = value;
    int i = size;
    while (i > 1 && heap[i] > heap[[1]]) {
        std::swap(heap[i], heap[i / 2]);
        i = i / 2;
    }
}

Drag options to blanks, or click blank then click option'

Asize

Bi - 1

Ci + 1

Di / 2

Attempts:

3 left

💡 Hint

Common Mistakes

Using i - 1 or i + 1 instead of i / 2 to find the parent index.

Comparing with the wrong index causing incorrect heap structure.

In a heap stored as an array, the parent of node at index i is at index i / 2. This is why we compare heap[i] with heap[i / 2] to maintain the max heap property.

2fill in blank

medium

Complete the code to extract the maximum element from a max heap.

DSA C++

int extractMax(int heap[], int& size) {
    if (size == 0) return -1;
    int maxVal = heap[1];
    heap[1] = heap[size];
    size--;
    int i = 1;
    while (true) {
        int left = 2 * i;
        int right = 2 * i + 1;
        int largest = i;
        if (left <= size && heap[left] > heap[[1]]) largest = left;
        if (right <= size && heap[right] > heap[largest]) largest = right;
        if (largest == i) break;
        std::swap(heap[i], heap[largest]);
        i = largest;
    }
    return maxVal;
}

Drag options to blanks, or click blank then click option'

Aright

Bleft

Ci

Dsize

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing left child with right child instead of current node.

Using wrong indices causing heap property violation.

We compare the left child heap[left] with the current node heap[i] to find the largest value among them. This helps in maintaining the max heap property during extraction.

3fill in blank

hard

Fix the error in the code that checks if a sorted array can efficiently support insertion.

DSA C++

bool canInsertEfficiently(const std::vector<int>& sortedArr) {
    // Insertion in sorted array requires shifting elements
    // Time complexity is O([1])
    return false;
}

Drag options to blanks, or click blank then click option'

A1

Bn

Clog n

Dn log n

Attempts:

3 left

💡 Hint

Common Mistakes

Assuming insertion is logarithmic time in a sorted array.

Confusing search time with insertion time.

Insertion in a sorted array requires shifting elements to maintain order, which takes linear time O(n). This is inefficient compared to heap insertion.

4fill in blank

hard

Fill both blanks to complete the code that compares insertion time in a sorted array and a heap.

DSA C++

int insertionTimeSortedArray(int n) {
    return n * [1]; // shifting elements
}

int insertionTimeHeap(int n) {
    return [2]; // heap insertion time
}

Drag options to blanks, or click blank then click option'

A1

Blog n

Cn

Dn log n

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'n' for heap insertion time instead of 'log n'.

Using 'log n' for shifting cost instead of constant time per element.

In a sorted array, insertion requires shifting n elements by 1 step each, so time is proportional to n * 1 = n. In a heap, insertion takes O(log n) time due to heapify operations.

5fill in blank

hard

Fill all three blanks to complete the code that demonstrates why heaps are better for priority queue operations than sorted arrays.

DSA C++

struct PriorityQueue {
    std::vector<int> data;

    void insert(int value) {
        data.push_back(value);
        int i = data.size() - 1;
        while (i > 0 && data[i] > data[[1]]) {
            std::swap(data[i], data[[2]]);
            i = [3];
        }
    }
};

Drag options to blanks, or click blank then click option'

Ai / 2

Bi - 1

C(i - 1) / 2

Di + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using one-based indexing formula i / 2 instead of zero-based.

Using incorrect parent index causing infinite loops.

In a heap implemented as a vector, the parent of node at index i is at index (i - 1) / 2. This is used to maintain the heap property during insertion.