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