Heap sort algorithm.

Heap sort use case.


Heap sort algorithm is a comparison-based sorting method based on Binary Heap data structure.

A binary tree is corresponding a heap data structure if it is a complete binary tree and all nodes in the tree have the property that they are greater than their children.

Heap sort algorithm.



Heap sort is similar to selection sort in finding minimum element and putting it at the beginning, then repeating the same process for the others elements. Sometimes Heap sort is called improved selection sort.


Heap Sort Python code:



def heapify(arr, n, i):
    # Finding largest among root and children
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    # If root is not largest, swap with largest and continue
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


def heapSort(arr):
    n = len(arr)

    # Building max heap
    for i in range(n//2, -1, -1):
        heapify(arr, n, i)

    for i in range(n-1, 0, -1):
        # Swap
        arr[i], arr[0] = arr[0], arr[i]

        # Heapify root element
        heapify(arr, i, 0)


arr = [-10, 35, 0, 13, -7]
heapSort(arr)
n = len(arr)
print("Sorted elements in ascending order")
for i in range(n):
    print("%d " % arr[i], end='')

OUT: Sorted elements in ascending order:
-10 -7 0 13 35





See also related topics: