Heap sort algorithm in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to build a max heap from an unsorted array.

Data Structures Theory

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

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

Ai

Bn

C0

Dlen(arr)

Attempts:

3 left

💡 Hint

Common Mistakes

Using the length of the array instead of the current index.

Passing 0 or n incorrectly as the node index.

The heapify function is called starting from the last non-leaf node, which is at index i, moving upwards to the root.

2fill in blank

medium

Complete the code to swap the root of the heap with the last element during heap sort.

Data Structures Theory

def heap_sort(arr):
    n = len(arr)
    build_max_heap(arr)
    for i in range(n-1, 0, -1):
        arr[0], arr[[1]] = arr[[1]], arr[0]
        heapify(arr, i, 0)

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

A1

Bn

Ci

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping with index 0 or 1 instead of the current last element.

Using the length of the array instead of the current index.

During each iteration, the root element at index 0 is swapped with the element at index i, which moves the largest element to its correct sorted position.

3fill in blank

hard

Fix the error in the heapify function to correctly maintain the max heap property.

Data Structures Theory

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] [1] arr[largest]:
        largest = left

    if right < n and arr[right] [1] arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

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

A>

B<

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using less than operator which builds a min heap instead.

Using equality or not equal operators which do not maintain heap property.

The heapify function compares child nodes with the current largest node. To maintain a max heap, it should check if the child is greater than the current largest.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps each element to its squared value if the element is even.

Data Structures Theory

squares = {x: x[1]2 for x in range(1, 11) if x [2] 2 == 0}

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

A**

B%

C//

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using division instead of modulus to check even numbers.

Using addition instead of power to square numbers.

The operator ** is used to square the number, and % checks if the number is even by verifying the remainder is zero.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps uppercase strings to their lengths if length is greater than 3.

Data Structures Theory

result = [1]: [2] for s in words if len(s) [3] 3}

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

As.upper()

Blen(s)

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using lowercase strings as keys instead of uppercase.

Using less than operator instead of greater than.

Using the string itself as value instead of its length.

The key is the uppercase version of the string using s.upper(), the value is the length len(s), and the condition checks if length is greater than 3 using >.

Practice

1. What is the main data structure used in the Heap sort algorithm to organize elements during sorting?

easy

A. Queue

B. Heap

C. Stack

D. Linked List

Solution

1. Step 1: Understand the core structure of Heap sort

   Heap sort organizes elements using a special tree-based structure called a heap.

2. Step 2: Identify the specific heap type used

   Heap sort uses a max heap to repeatedly extract the largest element for sorting.

3. Final Answer:

   Heap -> Option B

4. Quick Check:

   Heap = Heap sort main structure [OK]

Hint: Heap sort always uses a heap structure [OK]

Common Mistakes:

• Confusing heap with queue or stack
• Thinking linked list is used for sorting
• Assuming array is the main structure

2. Which of the following is the correct first step in the Heap sort algorithm?

easy

A. Build a max heap from the input array

B. Sort the array using bubble sort

C. Reverse the array elements

D. Split the array into two halves

Solution

1. Step 1: Identify the initial operation in Heap sort

   The algorithm starts by building a max heap from the unsorted input array.

2. Step 2: Understand why this step is important

   Building a max heap ensures the largest element is at the root, ready for extraction.

3. Final Answer:

   Build a max heap from the input array -> Option A

4. Quick Check:

   First step = Build max heap [OK]

Hint: Heap sort always starts by building a max heap [OK]

Common Mistakes:

• Confusing with other sorting algorithms like bubble sort
• Trying to reverse or split array first
• Skipping heap construction

3. Consider the array [4, 10, 3, 5, 1]. After building the max heap in Heap sort, what is the root element of the heap?

medium

A. 5

B. 4

C. 10

D. 3

Solution

1. Step 1: Build max heap from the array

   Heap sort builds a max heap where the largest element is at the root. For [4, 10, 3, 5, 1], 10 is the largest.

2. Step 2: Confirm root element

   After heapifying, 10 becomes the root element of the max heap.

3. Final Answer:

   10 -> Option C

4. Quick Check:

   Max heap root = largest element = 10 [OK]

Hint: Max heap root is always the largest element [OK]

Common Mistakes:

• Choosing first array element as root
• Confusing max heap with min heap
• Not heapifying properly

4. Identify the error in this Heap sort step: "After building the max heap, the algorithm swaps the root with the last element but forgets to heapify the reduced heap."

medium

A. Heapify must be called after each swap to maintain heap property

B. Heap sort does not use heapify at all

C. Swapping root with last element is not part of Heap sort

D. No error, this is correct

Solution

1. Step 1: Understand the Heap sort process after swapping

   After swapping the root with the last element, the heap property may break in the reduced heap.

2. Step 2: Identify the missing step

   Heapify must be called on the reduced heap to restore the max heap property before next extraction.

3. Final Answer:

   Heapify must be called after each swap to maintain heap property -> Option A

4. Quick Check:

   Heapify needed after swap [OK]

Hint: Always heapify after swapping root in Heap sort [OK]

Common Mistakes:

• Skipping heapify after swap
• Thinking swap alone sorts the array
• Confusing heapify with building heap

5. You have an array with many duplicate elements. How does Heap sort handle duplicates during sorting?

hard

A. Duplicates are kept in their original relative order (stable sort)

B. Heap sort removes duplicates automatically

C. Duplicates cause Heap sort to fail

D. Duplicates may change order because Heap sort is not stable

Solution

1. Step 1: Understand stability in sorting algorithms

   A stable sort keeps duplicates in original order; an unstable sort may reorder them.

2. Step 2: Analyze Heap sort stability

   Heap sort is not stable because heap operations can reorder equal elements arbitrarily.

3. Final Answer:

   Duplicates may change order because Heap sort is not stable -> Option D

4. Quick Check:

   Heap sort is unstable, duplicates reorder [OK]

Hint: Heap sort is not stable; duplicates can reorder [OK]

Common Mistakes:

• Assuming Heap sort is stable
• Thinking duplicates cause errors
• Believing duplicates are removed