Heap Sort Algorithm in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to swap two elements in the array.

DSA Java

int temp = arr[[1]];
arr[[1]] = arr[j];
arr[j] = temp;

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

Ai

B0

Cj

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using j instead of i causes swapping the same element.

Using 0 or n causes index errors.

The variable i is used to swap the element at index i with the element at index j.

2fill in blank

medium

Complete the code to find the left child index in the heap.

DSA Java

int left = 2 * i [1] 1;

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

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction - instead of addition.

Using multiplication or division operators incorrectly.

The left child index in a heap is calculated as 2 * i + 1.

3fill in blank

hard

Fix the error in the condition to check if right child exists in the heap.

DSA Java

if (right [1] n && arr[right] > arr[largest]) {

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

A>

B<=

C>=

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using greater than or equal operators causes index out of bounds errors.

Using greater than operator reverses the logic.

The right child index must be less than n to exist in the heap.

4fill in blank

hard

Fill both blanks to complete the heapify recursive call and swap.

DSA Java

if (largest != i) {
    int swap = arr[i];
    arr[i] = arr[[1]];
    arr[[2]] = swap;
    heapify(arr, n, largest);
}

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

Alargest

Bi

Cn

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using i or n instead of largest in swap causes incorrect heap structure.

Not swapping correctly breaks the heap property.

We swap the element at i with the element at largest, then recursively heapify at largest.

5fill in blank

hard

Fill all three blanks to complete the heap sort main loop.

DSA Java

for (int i = n - 1; i > 0; i--) {
    int temp = arr[0];
    arr[0] = arr[[1]];
    arr[[2]] = temp;
    heapify(arr, [3], 0);
}

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

Ai

B0

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using n instead of i in swap or heapify causes wrong sorting.

Swapping with 0 twice does nothing.

Swap the root arr[0] with arr[i], then heapify the reduced heap of size i.

Practice

1. What is the main purpose of the heap in the Heap Sort algorithm?

easy

A. To count the number of elements in the array

B. To store elements in sorted order permanently

C. To efficiently find and remove the largest (or smallest) element

D. To reverse the array elements

Solution

1. Step 1: Understand heap property

   A heap is a special tree-based structure where the parent node is either greater (max-heap) or smaller (min-heap) than its children.

2. Step 2: Role in Heap Sort

   Heap Sort uses a max-heap to quickly find the largest element at the root, then removes it to build the sorted array.

3. Final Answer:

   To efficiently find and remove the largest (or smallest) element -> Option C

4. Quick Check:

   Heap = fast max/min retrieval [OK]

Hint: Heap always keeps largest or smallest element on top [OK]

Common Mistakes:

• Thinking heap stores sorted elements permanently
• Confusing heap with a simple array
• Assuming heap counts elements

2. Which of the following is the correct way to build a max heap from an array in Java?

easy

A. for (int i = 0; i < n; i++) heapify(arr, i, n);

B. for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, i, n);

C. for (int i = n - 1; i >= 0; i--) heapify(arr, i, n);

D. for (int i = 0; i < n / 2; i++) heapify(arr, i, n);

Solution

1. Step 1: Identify heapify starting point

   Heapify must start from the last non-leaf node, which is at index n/2 - 1, moving upwards.

2. Step 2: Loop direction and range

   The loop runs backwards from n/2 - 1 down to 0 to ensure all subtrees satisfy heap property.

3. Final Answer:

   for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, i, n); -> Option B

4. Quick Check:

   Build heap from last non-leaf node [OK]

Hint: Start heapify from n/2 - 1 down to 0 [OK]

Common Mistakes:

• Starting heapify from 0 upwards
• Heapifying leaf nodes unnecessarily
• Looping in wrong direction

3. What will be the output array after applying Heap Sort on [4, 10, 3, 5, 1]?

medium

A. [1, 3, 4, 5, 10]

B. [10, 5, 4, 3, 1]

C. [1, 4, 3, 5, 10]

D. [5, 10, 4, 3, 1]

Solution

1. Step 1: Build max heap from array

   Max heap of [4,10,3,5,1] is [10,5,3,4,1].

2. Step 2: Extract max and heapify repeatedly

   Remove 10, heapify remaining; then 5, then 4, then 3, then 1, resulting in sorted array [1,3,4,5,10].

3. Final Answer:

   [1, 3, 4, 5, 10] -> Option A

4. Quick Check:

   Heap Sort sorts ascending [OK]

Hint: Heap Sort outputs sorted array ascending [OK]

Common Mistakes:

• Confusing max heap array with sorted array
• Forgetting to heapify after extraction
• Assuming heap sort outputs descending by default

4. Identify the error in this heapify method snippet for max heap in Java:

void heapify(int[] arr, int i, int n) {
  int largest = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;
  if (left < n && arr[left] < arr[largest]) largest = left;
  if (right < n && arr[right] > arr[largest]) largest = right;
  if (largest != i) {
    int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
    heapify(arr, largest, n);
  }
}

medium

A. The swap logic is incorrect

B. The recursive call should be heapify(arr, i, n) instead of heapify(arr, largest, n)

C. The indices for left and right children are incorrect

D. The comparison for left child should be '>' instead of '<'

Solution

1. Step 1: Check comparison operators for max heap

   For max heap, parent should be greater than children, so we check if child > parent to update largest.

2. Step 2: Identify incorrect comparison

   The code uses 'arr[left] < arr[largest]' which is wrong; it should be 'arr[left] > arr[largest]'.

3. Final Answer:

   The comparison for left child should be '>' instead of '<' -> Option D

4. Quick Check:

   Max heap needs '>' comparison [OK]

Hint: Max heap compares child > parent [OK]

Common Mistakes:

• Using '<' instead of '>' for max heap
• Wrong recursive call index
• Incorrect child index calculation

5. Given an array with many duplicate elements, how does Heap Sort behave and what is the time complexity in the worst case?

hard

A. Heap Sort handles duplicates normally with O(n log n) worst-case time

B. Heap Sort fails with duplicates and runs in O(n^2)

C. Heap Sort sorts duplicates faster with O(n) time

D. Heap Sort requires extra space for duplicates, increasing complexity

Solution

1. Step 1: Understand duplicates in Heap Sort

   Heap Sort treats duplicates like any other elements; duplicates do not affect the heap property or sorting steps.

2. Step 2: Time complexity with duplicates

   Heap Sort always runs in O(n log n) time in worst case, regardless of duplicates.

3. Final Answer:

   Heap Sort handles duplicates normally with O(n log n) worst-case time -> Option A

4. Quick Check:

   Duplicates do not affect Heap Sort time [OK]

Hint: Duplicates don't change Heap Sort time complexity [OK]

Common Mistakes:

• Thinking duplicates cause slower sorting
• Assuming Heap Sort needs extra space for duplicates
• Confusing Heap Sort with unstable sorts