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 an element into a max heap array.

DSA C#

void Insert(int[] heap, int value, ref int size) {
    heap[size] = value;
    int current = size;
    size++;
    while (current > 0 && heap[current] > heap[[1]]) {
        int parent = (current - 1) / 2;
        int temp = heap[current];
        heap[current] = heap[parent];
        heap[parent] = temp;
        current = parent;
    }
}

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

Acurrent

Bparent

Csize

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with current instead of parent.

Using size as index in comparison.

Using 0 instead of parent index.

We compare the current node with its parent 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, ref int size) {
    if (size == 0) return -1;
    int max = heap[0];
    heap[0] = heap[size - 1];
    size--;
    int current = 0;
    while (true) {
        int left = 2 * current + 1;
        int right = 2 * current + 2;
        int largest = current;
        if (left < size && heap[left] > heap[[1]]) largest = left;
        if (right < size && heap[right] > heap[largest]) largest = right;
        if (largest == current) break;
        int temp = heap[current];
        heap[current] = heap[largest];
        heap[largest] = temp;
        current = largest;
    }
    return max;
}

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

Asize

Bleft

Cright

Dcurrent

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing left child with right child directly.

Using size as index in comparison.

Comparing with left or right instead of current.

We compare the left child with the current node to find the largest among them.

3fill in blank

hard

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

DSA C#

bool CanInsertEfficiently(int[] sortedArray) {
    // 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

Blog n

Cn

Dn log n

Attempts:

3 left

💡 Hint

Common Mistakes

Assuming insertion is O(1) or O(log n) in sorted arrays.

Confusing search time with insertion time.

Insertion in a sorted array requires shifting elements, which takes linear time O(n).

4fill in blank

hard

Fill both blanks to complete the explanation of why heaps are better than sorted arrays for priority queues.

DSA C#

Heaps allow [1] insertion and [2] extraction of the maximum element, both in O(log n) time, while sorted arrays have O(n) insertion and O(1) extraction.

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

Afast

Bslow

Cefficient

Dinefficient

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing 'slow' or 'inefficient' for heap operations.

Confusing heap and sorted array operation times.

Heaps provide efficient insertion and extraction operations, both in O(log n) time, unlike sorted arrays.

5fill in blank

hard

Fill all three blanks to complete the code that builds a max heap from an unsorted array.

DSA C#

void BuildMaxHeap(int[] arr, int size) {
    for (int i = size / 2 - 1; i >= [1]; i--) {
        Heapify(arr, size, [2]);
    }
}

void Heapify(int[] arr, int size, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

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

    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        Heapify(arr, size, [3]);
    }
}

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

A0

Bi

C1

Dsize

Elargest

Attempts:

3 left

💡 Hint

Common Mistakes

Starting loop from size instead of 0.

Passing wrong index to Heapify.

Not calling Heapify recursively on the largest child.

The loop starts from the last non-leaf node at index 0, calling Heapify on each node i, and Heapify recursively calls itself on the largest child.

Practice

1. Why do we use a heap instead of just a sorted array for priority queue operations?

easy

A. Because heaps do not allow duplicate elements

B. Because heaps store elements in sorted order permanently

C. Because heaps allow faster insertion and deletion of the highest priority element

D. Because heaps use less memory than arrays

Solution

1. Step 1: Understand insertion and deletion in sorted arrays

   Inserting or deleting an element in a sorted array requires shifting elements, which takes O(n) time.

2. Step 2: Compare with heap operations

   Heaps allow insertion and deletion of the highest priority element in O(log n) time by maintaining a partial order.

3. Final Answer:

   Because heaps allow faster insertion and deletion of the highest priority element -> Option C

4. Quick Check:

   Heap operations faster than sorted array insert/delete [OK]

Hint: Heaps speed up insert/delete compared to sorted arrays [OK]

Common Mistakes:

• Thinking heaps keep all elements fully sorted
• Assuming heaps use less memory than arrays
• Believing heaps disallow duplicates

2. Which of the following is the correct syntax to insert an element into a min-heap in C# using a PriorityQueue named pq?

easy

A. pq.Add(5);

B. pq.Enqueue(5, 5);

C. pq.Insert(5);

D. pq.Push(5);

Solution

1. Step 1: Recall PriorityQueue method for insertion

   In C#, PriorityQueue uses Enqueue(item, priority) to insert elements.

2. Step 2: Check options for correct method and parameters

   Only pq.Enqueue(5, 5); matches the correct syntax for insertion with priority.

3. Final Answer:

   pq.Enqueue(5, 5); -> Option B

4. Quick Check:

   Use Enqueue(item, priority) to insert in PriorityQueue [OK]

Hint: Use Enqueue(item, priority) to insert in C# PriorityQueue [OK]

Common Mistakes:

• Using Insert or Add methods which don't exist for PriorityQueue
• Forgetting to provide priority value
• Using Push which is not a C# PriorityQueue method

3. What is the output of the following C# code snippet?

var pq = new PriorityQueue();
pq.Enqueue(10, 10);
pq.Enqueue(5, 5);
pq.Enqueue(20, 20);
int first = pq.Dequeue();
int second = pq.Dequeue();
Console.WriteLine($"{first} {second}");

medium

A. 5 10

B. 10 5

C. 20 10

D. 10 20

Solution

1. Step 1: Understand PriorityQueue behavior

   In C#, PriorityQueue is a min-heap by default, so Dequeue returns elements with the smallest priority first.

2. Step 2: Trace enqueue and dequeue operations

   Enqueued (10,10), (5,5), (20,20). Dequeue returns 5 (priority 5), then 10 (priority 10).

3. Final Answer:

   5 10 -> Option A

4. Quick Check:

   Dequeue returns elements in ascending priority order [OK]

Hint: Dequeue returns smallest priority first in C# PriorityQueue [OK]

Common Mistakes:

• Assuming dequeue returns highest priority first (max-heap)
• Mixing up item and priority values
• Thinking enqueue order determines dequeue order

4. The following code tries to remove the highest priority element from a sorted array but runs into performance issues. What is the main problem?

List<int> sortedList = new List<int>{1, 3, 5, 7, 9};
int highest = sortedList[sortedList.Count - 1];
sortedList.RemoveAt(sortedList.Count - 1);

medium

A. Removing the last element is O(1), but inserting is slow

B. Removing the last element in a list is O(n) and slow

C. Accessing the last element is O(n) and slow

D. The list is not sorted, so removal is incorrect

Solution

1. Step 1: Analyze removal operation on List

   Removing the last element with RemoveAt(last index) is O(1) because no shifting is needed.

2. Step 2: Consider insertion cost in sorted list

   Inserting new elements to keep list sorted requires shifting and is O(n), causing performance issues.

3. Final Answer:

   Removing the last element is O(1), but inserting is slow -> Option A

4. Quick Check:

   Removal at end fast; insertion in sorted list slow [OK]

Hint: Removal at end is fast; insertion in sorted list is slow [OK]

Common Mistakes:

• Thinking removal at end is O(n)
• Confusing access time with removal time
• Assuming list is unsorted

5. You have a large stream of numbers arriving continuously. You want to always quickly find and remove the smallest number seen so far. Why is a heap better than maintaining a sorted array for this task?

hard

A. Because heaps do not allow duplicate numbers

B. Because heaps keep all elements fully sorted at all times

C. Because sorted arrays use more memory than heaps

D. Because heaps allow O(log n) insertion and removal, while sorted arrays require O(n) insertion

Solution

1. Step 1: Consider insertion cost in sorted arrays

   Inserting a new number in a sorted array requires shifting elements, which is O(n).

2. Step 2: Compare with heap insertion and removal

   Heaps insert and remove the smallest element in O(log n) time by maintaining partial order.

3. Step 3: Understand why heaps suit streams

   For continuous streams, efficient insert and remove operations are critical, making heaps better.

4. Final Answer:

   Because heaps allow O(log n) insertion and removal, while sorted arrays require O(n) insertion -> Option D

5. Quick Check:

   Heap insert/remove O(log n) beats sorted array O(n) insert [OK]

Hint: Heap insert/remove O(log n) beats sorted array O(n) insert [OK]

Common Mistakes:

• Thinking heaps keep elements fully sorted
• Assuming memory usage differs significantly
• Believing heaps disallow duplicates