Heap Sort Algorithm in DSA Python - 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 repeatedly extract the largest element and place it at the end of the list, sorting the list in ascending order.

beginner

What is a max heap?

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

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 allows us to easily remove the largest element and place it at the end of the array, then fix the heap to find the next largest.

intermediate

What is the time complexity of Heap Sort and why?

Heap Sort has a time complexity of O(n log n). Building the heap takes O(n), and each of the n removals of the largest element requires O(log n) to restore the heap property.

intermediate

What is the space complexity of Heap Sort?

Heap Sort has a space complexity of O(1) because it sorts the array in place without needing extra space proportional to the input size.

What data structure does Heap Sort use to sort elements?

A Linked List

B Heap

C Queue

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 At the root

B At the leaf nodes

C In the middle level

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 Reverse the array

B Swap the first and last elements

C Sort the array using bubble sort

D Build a max heap from the input array

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

What is the time complexity of Heap Sort?

A O(n^2)

B O(log n)

C O(n 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 the input size?

A No, it sorts in place

B Yes, it needs extra arrays

C Yes, it uses linked lists

D No, but it uses recursion stack

Heap Sort sorts the array in place and uses only a constant amount of 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 heapify process in the Heap Sort Algorithm?

easy

A. To reverse the array elements

B. To swap the first and last elements of the array

C. To build a max-heap or min-heap from an unsorted array

D. To count the number of elements in the array

Solution

1. Step 1: Understand heapify's role

   Heapify rearranges elements to satisfy the heap property, making the array a max-heap or min-heap.

2. Step 2: Connect heapify to heap sort

   Heap sort uses heapify to prepare the array for sorting by ensuring the largest (or smallest) element is at the root.

3. Final Answer:

   To build a max-heap or min-heap from an unsorted array -> Option C

4. Quick Check:

   Heapify = build heap [OK]

Hint: Heapify builds the heap structure before sorting [OK]

Common Mistakes:

• Thinking heapify swaps elements randomly
• Confusing heapify with sorting step
• Assuming heapify counts elements

2. Which of the following is the correct way to call the heapify function in Python for an array arr of size n at index i?

easy

A. heapify(arr, n, i)

B. heapify(i, arr, n)

C. heapify(arr, i, n)

D. heapify(n, i, arr)

Solution

1. Step 1: Recall heapify function signature

   Heapify is usually defined as heapify(array, size, index) to adjust the heap at index.

2. Step 2: Match parameters order

   The correct order is array first, then size, then index to correctly access elements and heap size.

3. Final Answer:

   heapify(arr, n, i) -> Option A

4. Quick Check:

   heapify(array, size, index) = heapify(arr, n, i) [OK]

Hint: Remember: array, size, then index in heapify call [OK]

Common Mistakes:

• Mixing parameter order
• Passing index before array
• Confusing size and index positions

3. What will be the output of the following Python code snippet using heap sort?

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

arr = [4, 10, 3, 5, 1]
heapSort(arr)
print(arr)

medium

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

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

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

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

Solution

1. Step 1: Build max heap from array

   Heapify rearranges array to max heap: [10, 5, 3, 4, 1]

2. Step 2: Extract elements and heapify

   Swap root with last element and heapify repeatedly to sort ascending: final array is [1, 3, 4, 5, 10]

3. Final Answer:

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

4. Quick Check:

   Heap sort output = sorted array ascending [OK]

Hint: Heap sort outputs sorted array in ascending order [OK]

Common Mistakes:

• Expecting max heap array as final output
• Confusing heapify step with final sort
• Ignoring the swap and heapify loop

4. Identify the error in the following heap sort code snippet:

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l <= n and arr[l] > arr[largest]:
        largest = l
    if r <= n and arr[r] > arr[largest]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

medium

A. The condition should be 'l < n' and 'r < n' instead of 'l <= n' and 'r <= n'

B. The swap operation is missing

C. The function should return a value

D. The indices l and r are calculated incorrectly

Solution

1. Step 1: Check index boundary conditions

   Array indices go from 0 to n-1, so conditions must be 'l < n' and 'r < n' to avoid index error.

2. Step 2: Identify impact of wrong condition

   Using 'l <= n' or 'r <= n' can cause index out of range error when l or r equals n.

3. Final Answer:

   The condition should be 'l < n' and 'r < n' instead of 'l <= n' and 'r <= n' -> Option A

4. Quick Check:

   Index check uses less than n, not less or equal [OK]

Hint: Array indices go up to n-1, use '< n' not '<= n' [OK]

Common Mistakes:

• Using <= instead of < for array bounds
• Forgetting to swap elements
• Expecting heapify to return a value

5. Given an array with duplicate elements [4, 10, 4, 5, 1], how does heap sort handle duplicates, and what will be the sorted output?

hard

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

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

C. [1, 4, 5, 10]

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

Solution

1. Step 1: Understand heap sort with duplicates

   Heap sort treats duplicates as normal values and sorts them in ascending order without removal.

2. Step 2: Sort the array including duplicates

   Sorting [4, 10, 4, 5, 1] results in [1, 4, 4, 5, 10], preserving duplicates in order.

3. Final Answer:

   [1, 4, 4, 5, 10] -> Option B

4. Quick Check:

   Heap sort keeps duplicates, sorts ascending [OK]

Hint: Heap sort keeps duplicates, sorts all elements [OK]

Common Mistakes:

• Assuming duplicates are removed
• Expecting unsorted output with duplicates
• Confusing duplicates with errors