Heap Sort Advanced Tutorial

Heap sort is a comparison-based sorting technique based on a Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for the remaining elements.

Key Concepts

Binary Heap: A complete binary tree which satisfies the heap ordering property.
Heap Property: For a max heap, the value of each node is greater than or equal to the values of its children, and the same property is true for the min heap.
Heapify: The process of converting an array into a heap.

Steps of Heap Sort

Build a Max Heap: Convert the input array into a max heap.
Extract Elements: One by one extract elements from the heap.

Building a Max Heap

To build a max heap from an array, we start from the last non-leaf node and call the heapify procedure for each node.

def heapify(arr, n, i):
    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 largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

Extracting Elements

To extract elements from the heap, we swap the root of the heap with the last element of the heap and reduce the size of the heap by 1. We then heapify the root of the heap.

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

    for i in range(n, -1, -1):
        heapify(arr, n, i)

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

Complexity Analysis

Time Complexity: O(n log n)
Space Complexity: O(1)