Heap Concept Structure and Properties in DSA Java - Interactive Practice

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 value, int size) {
    heap[size] = value;
    int current = size;
    while (current > 0 && heap[current] [1] heap[(current - 1) / 2]) {
        int temp = heap[current];
        heap[current] = heap[(current - 1) / 2];
        heap[(current - 1) / 2] = temp;
        current = (current - 1) / 2;
    }
}

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

A<=

B<

C>

D==

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' causes the heap to become a min heap.

Using '==' does not maintain heap property.

Not swapping when necessary.

In a max heap, the inserted element is compared with its parent, and if it is greater, they are swapped to maintain the max heap property.

2fill in blank

medium

Complete the code to heapify a subtree rooted at index i in a max heap.

DSA Java

public void heapify(int[] heap, int size, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < size && heap[left] [1] heap[largest]) {
        largest = left;
    }

    if (right < size && heap[right] [1] heap[largest]) {
        largest = right;
    }

    if (largest != i) {
        int swap = heap[i];
        heap[i] = heap[largest];
        heap[largest] = swap;
        heapify(heap, size, largest);
    }
}

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

A<

B>

C==

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' causes min heap behavior.

Using '==' does not help find the largest.

Not checking array bounds before accessing children.

To maintain max heap property, we find the largest among root, left child, and right child. We compare children with '>' to find the largest.

3fill in blank

hard

Fix the error in the code that extracts the maximum element from a max heap.

DSA Java

public int extractMax(int[] heap, int size) {
    if (size <= 0) return -1;
    int max = heap[0];
    heap[0] = heap[size - 1];
    size = size - 1;
    heapify(heap, size, [1]);
    return max;
}

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

A0

Bsize

C1

Dsize - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting heapify at wrong index causes incorrect heap structure.

Using size or size-1 as index causes out-of-bound errors.

After replacing the root with the last element, heapify should start at index 0 to restore max heap property.

4fill in blank

hard

Fill both blanks to build a max heap from an unsorted array.

DSA Java

public void buildMaxHeap(int[] heap, int size) {
    for (int i = [1]; i >= 0; i--) {
        heapify(heap, size, [2]);
    }
}

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

Asize / 2 - 1

B0

Csize - 1

Dsize / 2

Attempts:

3 left

💡 Hint

Common Mistakes

Starting from size - 1 causes unnecessary heapify calls on leaf nodes.

Using 0 as start index causes no heap building.

Building a max heap starts from the last non-leaf node at index size/2 - 1 down to 0, calling heapify on each.

5fill in blank

hard

Fill all three blanks to implement heap sort using a max heap.

DSA Java

public void heapSort(int[] arr) {
    int n = arr.length;
    buildMaxHeap(arr, n);
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[[1]];
        arr[[2]] = arr[0];
        arr[0] = temp;
        heapify(arr, [3], 0);
    }
}

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

Ai

B0

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping wrong indices causes incorrect sorting.

Heapifying with wrong size or index breaks heap property.

In heap sort, swap the root with the last element (index i), then heapify the reduced heap of size i starting at root 0.

Practice

1. What is a key property of a max-heap data structure?

easy

A. The tree is always a complete binary tree but not necessarily balanced

B. The value of each parent node is less than or equal to its children

C. All leaf nodes have the same value

D. The value of each parent node is greater than or equal to its children

Solution

1. Step 1: Understand max-heap property

   A max-heap requires that every parent node's value is greater than or equal to its children.

2. Step 2: Compare options with max-heap definition

   The value of each parent node is greater than or equal to its children matches the max-heap property exactly, while others describe min-heap or unrelated properties.

3. Final Answer:

   The value of each parent node is greater than or equal to its children -> Option D

4. Quick Check:

   Max-heap parent ≥ children = A [OK]

Hint: Max-heap means parent node ≥ children nodes [OK]

Common Mistakes:

• Confusing max-heap with min-heap property
• Thinking leaf nodes must have same value
• Ignoring the complete binary tree requirement

2. Which of the following is the correct way to declare a min-heap using Java's PriorityQueue?

easy

A. PriorityQueue<Integer> minHeap = new PriorityQueue<>(Collections.reverseOrder());

B. PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.reverseOrder());

C. PriorityQueue<Integer> minHeap = new PriorityQueue<>();

D. PriorityQueue<Integer> minHeap = new PriorityQueue<>(Collections.naturalOrder());

Solution

1. Step 1: Recall Java PriorityQueue default behavior

   By default, PriorityQueue in Java is a min-heap, so no comparator is needed.

2. Step 2: Analyze options for min-heap declaration

   PriorityQueue<Integer> minHeap = new PriorityQueue<>(); uses default constructor, which creates a min-heap. A and B use reverseOrder creating max-heap, C uses non-existent Collections.naturalOrder().

3. Final Answer:

   PriorityQueue<Integer> minHeap = new PriorityQueue<>(); -> Option C

4. Quick Check:

   Default PriorityQueue = min-heap = D [OK]

Hint: Default PriorityQueue in Java is min-heap [OK]

Common Mistakes:

• Using reverseOrder() creates max-heap, not min-heap
• Confusing naturalOrder() with reverseOrder()
• Adding unnecessary comparator for default min-heap

3. What will be the output of the following Java code snippet?

import java.util.PriorityQueue;
public class TestHeap {
  public static void main(String[] args) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    heap.add(30);
    heap.add(10);
    heap.add(20);
    System.out.print(heap.poll() + ", " + heap.poll() + ", " + heap.poll());
  }
}

medium

A. 20, 10, 30

B. 10, 20, 30

C. 30, 20, 10

D. 10, 30, 20

Solution

1. Step 1: Understand PriorityQueue behavior

   Java's PriorityQueue is a min-heap by default, so poll() returns the smallest element.

2. Step 2: Trace poll() calls

   Elements added: 30, 10, 20. First poll() returns 10, second 20, third 30.

3. Final Answer:

   10, 20, 30 -> Option B

4. Quick Check:

   poll() returns min element each time = 10,20,30 [OK]

Hint: poll() returns smallest element in min-heap [OK]

Common Mistakes:

• Assuming poll() returns elements in insertion order
• Confusing min-heap with max-heap behavior
• Not realizing poll() removes elements

4. Identify the error in the following code that attempts to create a max-heap using Java's PriorityQueue:

import java.util.PriorityQueue;
import java.util.Collections;
public class MaxHeapExample {
  public static void main(String[] args) {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
    maxHeap.add(5);
    maxHeap.add(15);
    maxHeap.add(10);
    System.out.println(maxHeap.poll());
  }
}

medium

A. PriorityQueue is not initialized with a comparator for max-heap

B. PriorityQueue cannot store Integer objects

C. poll() method does not exist for PriorityQueue

D. add() method cannot be used to insert elements

Solution

1. Step 1: Check PriorityQueue initialization

   The code initializes PriorityQueue without a comparator, so it defaults to min-heap.

2. Step 2: Identify max-heap creation mistake

   To create max-heap, PriorityQueue must be initialized with Collections.reverseOrder() comparator.

3. Final Answer:

   PriorityQueue is not initialized with a comparator for max-heap -> Option A

4. Quick Check:

   Missing comparator = B [OK]

Hint: Max-heap needs reverseOrder() comparator in PriorityQueue [OK]

Common Mistakes:

• Assuming default PriorityQueue is max-heap
• Thinking poll() method is invalid
• Believing add() cannot insert elements

5. Given a max-heap represented as an array: [50, 30, 40, 10, 20], which of the following arrays represents the heap after inserting the element 35 and re-heapifying?

hard

A. [50, 30, 40, 10, 20, 35]

B. [50, 35, 40, 10, 20, 30]

C. [50, 40, 30, 10, 20, 35]

D. [50, 40, 35, 10, 20, 30]

Solution

1. Step 1: Insert 35 at the end of the array

   Array becomes [50, 30, 40, 10, 20, 35].

2. Step 2: Re-heapify by comparing 35 with its parent

   Parent of index 5 is index 2 (40). Since 35 <= 40, no swap needed. Heap property is maintained.

3. Step 3: Check if bubbling up is needed

   Since 35 < 40, no bubble up occurs, so the array remains [50, 30, 40, 10, 20, 35]. However, this matches [50, 30, 40, 10, 20, 35], but [50, 30, 40, 10, 20, 35] is not the correct max-heap after insertion because 35 should bubble up if possible.

4. Step 4: Correct bubbling up

   Actually, 35 is less than 40, so no swap with parent. The heap remains [50, 30, 40, 10, 20, 35].

5. Final Answer:

   [50, 30, 40, 10, 20, 35] -> Option A

6. Quick Check:

   Insert 35 at end, parent(5)=40 >= 35, no bubble up = D [OK]

Hint: Insert at end, then bubble up to fix max-heap [OK]

Common Mistakes:

• Not bubbling up after insertion
• Swapping with wrong parent index
• Assuming insertion at root