← Back to Data Structures and Algorithms in Python

1. Introduction

Heap Sort is a comparison-based sorting algorithm that utilizes the properties of a binary heap data structure to sort arrays or lists in-place. It can be visualized as an improved selection sort, where the maximum element is repeatedly fetched from the unsorted section of the array and moved to the sorted section.

2. Implementation Steps

1. Convert the input array into a max heap.

2. Swap the first element (maximum value) with the last element in the unsorted section of the array.

3. Reduce the size of the unsorted section by one and convert the remaining part of the array back to a max heap.

4. Repeat the above two steps until the entire array is sorted.

3. Implementation in Python

def heapify(arr, n, i):
    """Function to turn an array into a max heap"""
    largest = i  # Initialize largest as root
    l = 2 * i + 1  # left child
    r = 2 * i + 2  # right child
    # Check if left child exists and is greater than the root
    if l < n and arr[i] < arr[l]:
        largest = l
    # Check if right child exists and is greater than the root
    if r < n and arr[largest] < arr[r]:
        largest = r
    # Change root if needed
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # Swap
        heapify(arr, n, largest)
def heap_sort(arr):
    n = len(arr)
    # Build a max heap
    for i in range(n, -1, -1):
        heapify(arr, n, i)
    # Extract elements from heap one by one
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print(arr)

Output:

[5, 6, 7, 11, 12, 13]

Explanation:

1. The function heapify is responsible for turning a portion of the array into a max heap. The function takes in the array, its length, and an index i. It ensures that the subtree rooted at index i is a max heap.

2. The main function heap_sort first constructs the max heap from the input array.

3. Once the max heap is formed, the first element (root of the heap) will contain the maximum value. This element is then swapped with the last element of the unsorted section.

4. After swapping, the size of the unsorted section is reduced by one and heapify is called again to ensure the reduced array still maintains the max heap property.

5. These steps are repeated until the entire array is sorted.

The Heap Sort algorithm runs in O(n log n) time complexity in the worst, average, and best cases, making it more efficient than simple comparison-based sorting algorithms like bubble sort, selection sort, or insertion sort.