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.
Python Knowledge Base: Make coding great again.
- Updated:
2024-07-26 by Andrey BRATUS, Senior Data Analyst.
Heap Sort Python code:
Heap Sort Python code output:
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.
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