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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert an element into a max heap array.

DSA Java

public void insert(int[] heap, int size, int value) {
    heap[size] = value;
    int current = 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'

A(current - 1) / 2

Bcurrent - 1

Ccurrent / 2

Dcurrent + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using current - 1 as parent index

Using current / 2 which is incorrect for zero-based arrays

The parent index in a heap is calculated as (current - 1) / 2. This helps maintain the heap property during insertion.

2fill in blank

medium

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

DSA Java

public int extractMax(int[] heap, int size) {
    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'

Aright

Bleft

Ccurrent

Dsize

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing left child with left index

Using size as index

We compare the left child with the current node to find the largest value to maintain the max heap property.

3fill in blank

hard

Fix the error in the code that checks if a sorted array can efficiently insert an element.

DSA Java

public boolean canInsertEfficiently(int[] sortedArray, int value) {
    int n = sortedArray.length;
    for (int i = 0; i < n; i++) {
        if (sortedArray[i] > value) {
            // Need to shift elements to insert
            return [1];
        }
    }
    return true;
}

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

A0

Btrue

Cnull

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Returning true incorrectly

Returning null or zero which are invalid boolean values

Inserting into a sorted array requires shifting elements, so it is not efficient. Hence, return false.

4fill in blank

hard

Fill both blanks to complete the code that shows why heap is better than sorted array for insert and extract max.

DSA Java

public class HeapVsSortedArray {
    public static void main(String[] args) {
        int[] sortedArray = {1, 3, 5, 7, 9};
        int[] heap = {9, 7, 5, 3, 1};
        // Insert in sorted array is O([1])
        // Insert in heap is O([2])
    }
}

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

An

Blog n

C1

Dn log n

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping the complexities

Using constant time for sorted array insertion

Insertion in a sorted array requires shifting elements, so it takes O(n). In a heap, insertion takes O(log n) due to heapify up.

5fill in blank

hard

Fill all three blanks to complete the code that compares extract max operation in sorted array and heap.

DSA Java

public class ExtractMaxComparison {
    public static void main(String[] args) {
        int[] sortedArray = {1, 3, 5, 7, 9};
        int[] heap = {9, 7, 5, 3, 1};
        // Extract max in sorted array is O([1])
        // Extract max in heap is O([2])
        // Sorted array requires [3] to maintain order after extraction
    }
}

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

A1

Blog n

Cshifting

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing extraction times

Ignoring shifting cost in sorted array

Extract max in a sorted array is O(1) because max is at the end, but maintaining order requires shifting elements. In a heap, extract max is O(log n) due to heapify down.

Practice

1. Why do we use a heap instead of just a sorted array when we need to repeatedly access the smallest element?

easy

A. Because a heap stores elements in sorted order all the time.

B. Because a sorted array uses less memory than a heap.

C. Because a heap allows faster insertion and deletion of the smallest element than a sorted array.

D. Because a sorted array can only store unique elements.

Solution

1. Step 1: Compare insertion and deletion times

   In a sorted array, inserting or deleting elements requires shifting many elements, which takes linear time (O(n)).

2. Step 2: Understand heap operations

   A heap allows insertion and deletion of the smallest element in logarithmic time (O(log n)) by maintaining a partial order.

3. Final Answer:

   Because a heap allows faster insertion and deletion of the smallest element than a sorted array. -> Option C

4. Quick Check:

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

Hint: Heap is faster for insert/delete than sorted array [OK]

Common Mistakes:

• Thinking heaps keep all elements fully sorted
• Believing sorted arrays have faster insertions
• Confusing memory usage with operation speed

2. Which of the following is the correct way to insert an element into a min-heap in Java?

easy

A. Add element anywhere and sort the entire array.

B. Add element at the end and then bubble it up to maintain heap property.

C. Insert element at the root and then bubble it down.

D. Replace the smallest element directly without reordering.

Solution

1. Step 1: Understand min-heap insertion

   Inserting into a min-heap involves adding the new element at the end of the heap (bottom level) to maintain the complete tree property.

2. Step 2: Restore heap property by bubbling up

   Then, bubble the new element up by swapping it with its parent until the min-heap property is restored.

3. Final Answer:

   Add element at the end and then bubble it up to maintain heap property. -> Option B

4. Quick Check:

   Insert by adding end + bubble up [OK]

Hint: Insert at end, then bubble up in min-heap [OK]

Common Mistakes:

• Trying to insert at root directly
• Sorting entire array after insertion
• Replacing smallest element without reordering

3. Consider the following Java code using a PriorityQueue (min-heap):

PriorityQueue<Integer> heap = new PriorityQueue<>();
heap.add(5);
heap.add(3);
heap.add(8);
heap.poll();
System.out.println(heap);

What will be printed?

medium

A. [5, 8]

B. [3, 8]

C. [8, 5]

D. [3, 5]

Solution

1. Step 1: Add elements to the heap

   Elements 5, 3, and 8 are added. The heap organizes them so the smallest is at the root.

2. Step 2: Remove the smallest element using poll()

   poll() removes the smallest element, which is 3.

3. Step 3: Remaining elements in the heap

   After removing 3, the heap contains 5 and 8. The internal order is [5, 8].

4. Final Answer:

   [5, 8] -> Option A

5. Quick Check:

   poll removes 3, heap left with 5 and 8 [OK]

Hint: poll() removes smallest; remaining elements printed [OK]

Common Mistakes:

• Thinking poll() removes largest
• Assuming heap prints sorted array
• Confusing heap internal order with sorted order

4. The following code tries to remove the smallest element from a min-heap implemented as an array but has a bug:

int[] heap = {3, 5, 8, 10};
int smallest = heap[0];
heap[0] = heap[heap.length - 1];
// Missing heapify down step here
System.out.println(smallest);

What is the main problem?

medium

A. The smallest element is not at index 0.

B. The array length is not updated after removal.

C. The code tries to remove the largest element instead.

D. The heap is not restructured after removing the root, breaking heap property.

Solution

1. Step 1: Identify removal process

   The code removes the root (smallest element) by replacing it with the last element in the array.

2. Step 2: Check heap property maintenance

   After replacement, the heap property must be restored by heapifying down, which is missing here.

3. Step 3: Consequence of missing heapify

   Without heapify down, the heap structure is broken and future operations may fail.

4. Final Answer:

   The heap is not restructured after removing the root, breaking heap property. -> Option D

5. Quick Check:

   Missing heapify breaks heap after root removal [OK]

Hint: Always heapify down after removing root in heap [OK]

Common Mistakes:

• Assuming smallest is not at index 0
• Ignoring heapify after removal
• Forgetting to update array length

5. You have a large stream of numbers and want to always quickly find the top 5 smallest numbers seen so far. Why is using a sorted array inefficient, and how does a heap solve this problem efficiently?

hard

A. Sorted array requires shifting elements on each insertion; a max-heap of size 5 keeps top smallest efficiently.

B. Sorted array uses more memory; heap uses less memory for the same data.

C. Sorted array cannot store duplicates; heap can store duplicates easily.

D. Sorted array sorts only once; heap sorts continuously.

Solution

1. Step 1: Analyze sorted array insertion cost

   Inserting a new number into a sorted array requires shifting elements to keep order, which is slow (O(n)) for large data.

2. Step 2: Use a max-heap of fixed size

   A max-heap of size 5 can keep track of the top 5 smallest numbers by removing the largest when a smaller number arrives, all in O(log 5) time.

3. Step 3: Efficiency advantage

   This approach avoids shifting many elements and keeps operations fast even with a large stream.

4. Final Answer:

   Sorted array requires shifting elements on each insertion; a max-heap of size 5 keeps top smallest efficiently. -> Option A

5. Quick Check:

   Heap avoids shifts, keeps top 5 smallest fast [OK]

Hint: Use fixed-size max-heap to track smallest efficiently [OK]

Common Mistakes:

• Thinking sorted array is faster for insertions
• Confusing max-heap with min-heap usage
• Assuming duplicates are the main issue