Python Heap Sort Program - Complete Guide with Examples

Python - Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It works by first building a max heap (or min heap), then repeatedly extracting the maximum (or minimum) element from the heap and rebuilding the heap. Heap Sort is an efficient algorithm with a time complexity of O(n log n) for both average and worst cases.

Heap Sort Algorithm

The steps of the Heap Sort algorithm are as follows:

Build a max heap from the given list.
Swap the root element (maximum value) with the last element of the heap.
Reduce the heap size by 1 and rebuild the max heap for the remaining elements.
Repeat the above steps until the heap size becomes 1.

Python Program

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index

    # Check if left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left

    # Check if right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right

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

# Heap Sort function
def heap_sort(arr):
    n = len(arr)

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

    # One by one extract elements from heap
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # swap
        heapify(arr, i, 0)

# Input list
alist = [12, 11, 13, 5, 6]
print('Input List\n', alist)

# Sort the list
heap_sort(alist)
print('Sorted List\n', alist)

Explanation:

The heapify function is used to maintain the max heap property. It ensures that the root is the largest element, and recursively swaps elements to maintain the heap structure.
In the heap_sort function, we first build a max heap by calling the heapify function for each internal node of the heap (from the bottom up).
After building the heap, we repeatedly swap the root (maximum element) with the last element, reduce the heap size, and rebuild the heap for the remaining elements.
This process continues until the heap is empty, resulting in a sorted list.

Output

Input List
 [12, 11, 13, 5, 6]
Sorted List
 [5, 6, 11, 12, 13]

Summary