Heap Sort Algorithm

Introduction to Heap Sort

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. It involves building a heap from the input data and then repeatedly extracting the maximum element from the heap and rebuilding the heap until all elements are sorted. Heap sort has a time complexity of O(n log n) and is considered an efficient and reliable sorting algorithm.

---

Step-by-Step Process

Consider an array with the following elements:

[4, 10, 3, 5, 1]

To sort this array using heap sort, follow these steps:

1. Build a Max Heap: Convert the array into a max heap, where the largest element is at the root.
2. Extract Maximum Element: Swap the root (maximum element) with the last element of the heap and reduce the heap size by one. Then, heapify the root to maintain the max heap property.
3. Repeat: Repeat the extraction process until the heap size is reduced to one.

Let's apply these steps to the example array:

• Input array: [4, 10, 3, 5, 1]
• Build Max Heap: [10, 5, 3, 4, 1]
• Extract Max (10): Swap 10 with 1, Heapify: [5, 4, 3, 1, 10]
• Extract Max (5): Swap 5 with 1, Heapify: [4, 1, 3, 5, 10]
• Extract Max (4): Swap 4 with 1, Heapify: [3, 1, 4, 5, 10]
• Extract Max (3): Swap 3 with 1, Heapify: [1, 3, 4, 5, 10]
• Sorted array: [1, 3, 4, 5, 10]

---

Pseudo Code for Heap Sort

Below is the pseudo code for the heap sort algorithm:

function heapSort(array)
    n = length(array)
    for i = n / 2 - 1 to 0 do
        heapify(array, n, i)
    end for
    for i = n - 1 to 0 do
        swap(array[0], array[i])
        heapify(array, i, 0)
    end for
end function

function heapify(array, n, i)
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and array[left] > array[largest] then
        largest = left
    end if
    if right < n and array[right] > array[largest] then
        largest = right
    end if
    if largest != i then
        swap(array[i], array[largest])
        heapify(array, n, largest)
    end if
end function

Explanation:

• Initialize: The heapSort function starts by building a max heap from the input array. This is done by calling the heapify function for each non-leaf node, starting from the last non-leaf node to the root.
• Heapify: The heapify function ensures the subtree rooted at index i satisfies the max heap property. It compares the root with its left and right children and swaps them if necessary. The process is repeated recursively for the affected subtree.
• Extract Elements: After building the max heap, the largest element (root) is swapped with the last element of the heap. The heap size is reduced by one, and the heapify function is called to restore the max heap property. This process is repeated until the heap is empty.

---

Python Program to Implement Heap Sort

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

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

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

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

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

    for i in range(n // 2 - 1, -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)

# Example usage:
array = [4, 10, 3, 5, 1]
print("Original array:", array)
heap_sort(array)
print("Sorted array:", array)  # Output: [1, 3, 4, 5, 10]

This Python program defines functions to perform heap sort on an array. The heapify function maintains the max heap property, and the heap_sort function builds the heap and extracts elements to sort the array.