Heap Sort Practice Problems Online

A crucial element of the Heap_Sort is the construction of the heap itself. This is achieved by calling a heapify procedure on some nodes until all nodes satisfy the Max_Heap property( Any node must have a value less or equal to that of its parent ).

The node in position $2$ violates the heap property. Once heapify is applied to it, which position will it be in?

def Heap_Sort( A ):
    Build_Heap(A)
    for i in range(A.size, 1, -1): #loop down from A.size to 2
        # !MISSING LINE !!!
        A.size -= 1
        Max_Heapify(A,1)
    return list(A.A)

Consider the Heap_Sort method above. Given a list of numbers A it will construct a heap and sort them. One line is however missing(line 4). What line of code should be there in order to have a properly functioning Heap_Sort algorithm.

Note

The method assumes that the index of the first item is $1$ not $0$ .

A crucial element of the Heap_Sort is the construction of the heap itself. This is achieved by calling a heapify procedure on some nodes until all nodes satisfy the Max_Heap property( Any node must have a value less or equal to that of its parent ).

Suppose we have a an array with $51$ elements. At most, how many calls to heapify are required to convert it to a heap?

Concept Quizzes

Challenge Quizzes

Heap Sort

Sorting Algorithms

Concept Quizzes

Challenge Quizzes

Heap Sort