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 >.