Heap Sort Algorithm in DSA Java

Mental Model

Heap sort organizes data into a special tree shape called a heap to easily find the largest item and then sorts the list by repeatedly removing it.

Analogy: Imagine a pile of books stacked so the biggest book is always on top. You take the biggest book off, then rearrange the pile to keep the biggest book on top again, repeating until all books are sorted.

Array: [4, 10, 3, 5, 1]
Heap (max-heap):
       10
      /  \
     5    3
    / \
   4   1

Dry Run Walkthrough

Input: array: [4, 10, 3, 5, 1]

Goal: Sort the array in ascending order using heap sort

Step 1: Build max heap from array

[10, 5, 3, 4, 1]

Why: We rearrange the array so the largest value is at the root (index 0)

Step 2: Swap root (10) with last element (1), reduce heap size

[1, 5, 3, 4, 10]

Why: Move largest element to its correct final position at the end

Step 3: Heapify root to restore max heap property

[5, 4, 3, 1, 10]

Why: Fix heap so largest element is again at root for next extraction

Step 4: Swap root (5) with last element in heap (1), reduce heap size

[1, 4, 3, 5, 10]

Why: Place next largest element in correct position

Step 5: Heapify root to restore max heap

[4, 1, 3, 5, 10]

Why: Restore heap property for remaining elements

Step 6: Swap root (4) with last element in heap (3), reduce heap size

[3, 1, 4, 5, 10]

Why: Place next largest element in correct position

Step 7: Heapify root to restore max heap

[3, 1, 4, 5, 10]

Why: Heap property is already satisfied, no change

Step 8: Swap root (3) with last element in heap (1), reduce heap size

[1, 3, 4, 5, 10]

Why: Place next largest element in correct position

Step 9: Heapify root to restore max heap

[3, 1, 4, 5, 10]

Why: Heap property is satisfied, no change

Result:

[1, 3, 4, 5, 10] -- sorted array in ascending order

Annotated Code

DSA Java

public class HeapSort {

    public void sort(int[] arr) {
        int n = arr.length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // Extract elements from heap one by one
        for (int i = n - 1; i > 0; i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // call max heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }

    void heapify(int[] arr, int n, int i) {
        int largest = i; // Initialize largest as root
        int left = 2 * i + 1; // left child index
        int right = 2 * i + 2; // right child index

        // If left child is larger than root
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // If right child is larger than largest so far
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }

    // Driver code to test above
    public static void main(String[] args) {
        int[] arr = {4, 10, 3, 5, 1};
        HeapSort hs = new HeapSort();
        hs.sort(arr);

        // Print sorted array
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

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

Build max heap by heapifying from last parent to root

for (int i = n - 1; i > 0; i--) { swap root with arr[i]; heapify(arr, i, 0); }

Extract max element and restore heap for remaining elements

if (left < n && arr[left] > arr[largest]) { largest = left; }

Check if left child is larger than current largest

if (right < n && arr[right] > arr[largest]) { largest = right; }

Check if right child is larger than current largest

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

Swap and recursively heapify affected subtree

Output

1 3 4 5 10 

Complexity Analysis

Time: O(n log n) because building the heap takes O(n) and each of the n elements is extracted with O(log n) heapify operations

Space: O(1) because heap sort sorts the array in place without extra storage

vs Alternative: Compared to simple sorting like bubble sort O(n^2), heap sort is much faster for large data due to efficient max element extraction

Edge Cases

empty array

No operations performed, array remains empty

DSA Java

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

array with one element

Heapify runs once but no swaps needed, array stays same

DSA Java

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

array with all equal elements

Heapify finds no larger child, array remains unchanged but sorted

DSA Java

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

When to Use This Pattern

When you need to sort data efficiently and can use a tree-like structure to repeatedly find the largest or smallest item, heap sort is a strong choice because it uses a heap to organize data for quick extraction.

Common Mistakes

Mistake: Not building the max heap before sorting, causing incorrect order
Fix: Always build the max heap first by heapifying from the last parent node up to the root

Mistake: Not reducing the heap size after swapping the root with the last element
Fix: Decrease the heap size in the sorting loop to exclude sorted elements from heapify

Mistake: Not recursively heapifying after a swap, missing to restore heap property
Fix: Call heapify recursively on the affected subtree after swapping

Summary

Heap sort sorts an array by building a max heap and repeatedly extracting the largest element.

Use heap sort when you want an efficient in-place sorting algorithm with guaranteed O(n log n) time.

The key insight is to organize data as a heap so the largest element is always easy to find and remove.

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