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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert an element into a max heap represented as a vector.

DSA Rust

fn insert_max_heap(heap: &mut Vec<i32>, value: i32) {
    heap.push(value);
    let mut i = heap.len() - 1;
    while i > 0 && heap[i] > heap[(i - 1) / 2] {
        heap.swap(i, (i - 1) / 2);
        i = [1];
    }
}

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

Ai * 2 + 1

Bi + 1

C(i - 1) / 2

Di - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using i + 1 or i - 1 instead of parent index calculation.

Using child index formulas instead of parent index.

After swapping, we move up to the parent index, which is calculated as (i - 1) / 2 in a binary heap.

2fill in blank

medium

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

DSA Rust

fn extract_max(heap: &mut Vec<i32>) -> Option<i32> {
    if heap.is_empty() {
        return None;
    }
    let max = heap[0];
    let last = heap.pop().unwrap();
    if !heap.is_empty() {
        heap[0] = last;
        let mut i = 0;
        let n = heap.len();
        loop {
            let left = 2 * i + 1;
            let right = 2 * i + 2;
            let mut largest = i;
            if left < n && heap[left] > heap[largest] {
                largest = left;
            }
            if right < n && heap[right] > heap[largest] {
                largest = right;
            }
            if largest == i {
                break;
            }
            heap.swap(i, largest);
            i = [1];
        }
    }
    Some(max)
}

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

Aright

Bi + 1

Cleft

Dlargest

Attempts:

3 left

💡 Hint

Common Mistakes

Using i + 1 or fixed indices instead of the largest child index.

Not updating the index after swapping.

After swapping with the largest child, we continue heapifying down from the 'largest' index.

3fill in blank

hard

Fix the error in the code that tries to find the minimum element in a sorted array using binary search.

DSA Rust

fn find_min_sorted(arr: &[i32]) -> Option<i32> {
    if arr.is_empty() {
        return None;
    }
    let mut left = 0;
    let mut right = arr.len() - 1;
    while left < right {
        let mid = left + (right - left) / 2;
        if arr[mid] [1] arr[right] {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    Some(arr[left])
}

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

A<

B>

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' causes wrong half selection.

Using '==' or '!=' does not help in binary search logic.

In a rotated sorted array, if middle element is greater than right, the minimum is in the right half.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps words to their lengths only if length is greater than 3.

DSA Rust

{word: [1] for word in words if len(word) [2] 3}

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

Alen(word)

B>

C<

Dword

Attempts:

3 left

💡 Hint

Common Mistakes

Using the word itself as value instead of its length.

Using '<' instead of '>' in the condition.

We map each word to its length using len(word) and filter words with length greater than 3 using '>'.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps uppercase keys to values only if value is positive.

DSA Rust

result = [1]: [2] for k, v in data.items() if v [3] 0}}

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

Ak.upper()

Bv

C>

Dk

Attempts:

3 left

💡 Hint

Common Mistakes

Using original key instead of uppercase.

Using '<' or other operators instead of '>'.

Keys are converted to uppercase with k.upper(), values are v, and we filter values greater than 0.

Practice

1. What operation does a sorted array perform poorly compared to a heap when elements are frequently inserted?

medium

A. Finding the minimum element

B. Maintaining sorted order after insertion - O(n) shift vs O(log n) heap push

C. Deleting an element by value

D. Printing all elements in order

Solution

1. Step 1: Sorted array insert

   Inserting into a sorted array requires finding the position (O(log n) binary search) then shifting all elements to the right (O(n)). Total: O(n) per insert.

2. Step 2: Heap insert

   Heap push in Rust's BinaryHeap: O(log n) - add at end, sift up. No shifting needed.

3. Final Answer:

   Sorted array insert = O(n) due to shifting. Heap insert = O(log n). -> Option B

4. Quick Check:

   Sorted array: insert O(n). Heap: insert O(log n). Heap wins on dynamic data. [OK]

Hint: Sorted array insert = O(n) shift. Heap insert = O(log n). Heap exists for dynamic min/max. [OK]

Common Mistakes:

• Thinking sorted array insert is O(log n) because binary search finds position
• Forgetting the O(n) shift after finding position
• Confusing with sorted array search which is O(log n)

2. In Rust, std::collections::BinaryHeap is a max-heap by default. How do you use it as a min-heap?

medium

A. BinaryHeap::new_min()

B. Use BinaryHeap - wrap values in std::cmp::Reverse

C. Set a min_heap flag on initialization

D. Use BinaryHeap::with_capacity(0)

Solution

1. Step 1: Default is max-heap

   BinaryHeap<i32> pops the largest element. To get min-heap behavior, we need to reverse the ordering.

2. Step 2: Reverse wrapper

   std::cmp::Reverse<T> reverses the Ord comparison. BinaryHeap acts as a min-heap - Reverse(small) is 'larger' than Reverse(big).

3. Step 3: Usage

   heap.push(Reverse(val)); let Reverse(min_val) = heap.pop().unwrap();

4. Final Answer:

   BinaryHeap for min-heap. -> Option B

5. Quick Check:

   Min-heap in Rust = BinaryHeap. Reverse flips comparison. [OK]

Hint: Rust min-heap = BinaryHeap. Reverse flips Ord so smallest is 'greatest'. [OK]

Common Mistakes:

• Looking for a min_heap flag that doesn't exist
• Trying to negate values (works for numbers but not general types)
• Not knowing std::cmp::Reverse exists

3. What is the time complexity of finding the kth largest element repeatedly from a dynamic stream using a min-heap of size k?

hard

A. O(n²)

B. O(n log k)

C. O(n log n)

D. O(k²)

Solution

1. Step 1: Min-heap of size k

   Maintain a min-heap of the k largest elements seen. The heap top is always the kth largest.

2. Step 2: Per element cost

   For each of n elements: push O(log k). If heap size > k, pop O(log k). Total per element: O(log k).

3. Step 3: Total

   n elements × O(log k) = O(n log k).

4. Final Answer:

   O(n log k) -> Option B

5. Quick Check:

   n elements × O(log k) per heap op = O(n log k). [OK]

Hint: Stream kth largest: O(n log k). Heap size=k, each element costs O(log k). [OK]

Common Mistakes:

• Saying O(n log n) confusing with sorting the full array
• Saying O(n²) thinking of naive comparison approach
• Forgetting heap operations are O(log k) not O(k)

4. A heap guarantees O(1) access to the maximum (or minimum). What does a sorted array guarantee that a heap does NOT?

hard

A. O(1) insert

B. O(log n) delete-max

C. O(log n) search for an arbitrary value

D. O(1) pop of the second largest element

Solution

1. Step 1: Sorted array search

   Binary search on a sorted array: O(log n) for any value.

2. Step 2: Heap search

   A heap has no ordering except parent > children. Searching for an arbitrary value requires O(n) scan - no binary search possible.

3. Step 3: Trade-off

   Heap wins: O(1) max/min, O(log n) insert/delete. Sorted array wins: O(log n) arbitrary search.

4. Final Answer:

   O(log n) search for arbitrary value via binary search. -> Option C

5. Quick Check:

   Sorted array: binary search O(log n). Heap: arbitrary search O(n). [OK]

Hint: Heap: O(1) max, O(log n) insert. Sorted array: O(log n) search. Heap can't binary search. [OK]

Common Mistakes:

• Thinking heap supports O(log n) arbitrary search
• Forgetting sorted array insert is O(n)
• Thinking second largest is O(1) in heap (it's not)

5. Which algorithm specifically requires a heap (priority queue) and cannot be efficiently implemented with a sorted array due to dynamic insertions?

hard

A. Binary search

B. Merge sort

C. Dijkstra's shortest path algorithm

D. Quick sort

Solution

1. Step 1: Dijkstra's requirements

   Dijkstra's algorithm repeatedly extracts the node with minimum distance AND inserts newly discovered nodes. This mix of extract-min and insert is exactly what a heap optimizes.

2. Step 2: Sorted array Dijkstra

   Using a sorted array: extract-min O(1), but insert O(n) - total O(V²). With a binary heap: both O(log V) - total O((V+E) log V).

3. Final Answer:

   Dijkstra's - requires dynamic insert + extract-min, exactly heap's strength. -> Option C

4. Quick Check:

   Dijkstra = heap. Dynamic insert+extract-min is heap's core purpose. [OK]

Hint: Dijkstra needs dynamic insert+extract-min. Heap: O(log V) each. Sorted array: insert O(n). Heap wins. [OK]

Common Mistakes:

• Thinking binary search needs a heap
• Not knowing Dijkstra's core operation is repeated extract-min
• Confusing with merge sort which uses arrays not heaps