Heap Sort Algorithm in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Heap Sort Algorithm?

Heap Sort uses a special tree structure called a heap to sort elements. It builds a max heap to find the largest element quickly, then swaps it to the end and repeats for the rest.

beginner

What is a max heap?

A max heap is a binary tree where each parent node is greater than or equal to its children. This property helps find the largest element at the root easily.

intermediate

Why do we build a max heap before sorting in Heap Sort?

Building a max heap organizes the data so the largest element is at the root. This lets us remove the largest element and place it at the end of the array, sorting step by step.

intermediate

What is the time complexity of Heap Sort and why?

Heap Sort runs in O(n log n) time because building the heap takes O(n), and each of the n removals of the max element takes O(log n) to restore the heap.

beginner

What is the space complexity of Heap Sort?

Heap Sort uses O(1) extra space because it sorts the array in place without needing extra arrays or data structures.

What data structure does Heap Sort use to organize elements?

A Queue

B Heap

C Linked List

D Stack

Heap Sort uses a heap, specifically a max heap, to organize elements for sorting.

In a max heap, where is the largest element located?

A In the middle

B At the leaf nodes

C At the root

D At the last index

The largest element in a max heap is always at the root node.

What is the first step in Heap Sort?

A Swap first and last elements

B Build a linked list

C Sort the array directly

D Build a max heap from the array

Heap Sort starts by building a max heap from the input array.

What is the time complexity of Heap Sort?

A O(n log n)

B O(n^2)

C O(log n)

D O(n)

Heap Sort runs in O(n log n) time due to heap building and repeated heapify operations.

Does Heap Sort require extra space proportional to input size?

A No, it sorts in place

B Yes, it needs extra arrays

C Yes, it uses linked lists

D Yes, it uses recursion stack proportional to n

Heap Sort sorts the array in place using O(1) extra space.

Explain how Heap Sort uses a max heap to sort an array step by step.

Think about how the largest element moves to the end each time.

Describe the time and space complexity of Heap Sort and why it has those complexities.

Consider the cost of building and maintaining the heap.

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