Heap Sort Algorithm in Python.

Heap Sort is a comparison-based sorting algorithm that uses a Binary Heap data structure to sort elements in an array. In this article, we will discuss the algorithm in detail with Python code implementation.

Heap Sort Algorithm Explanation.

Heap Sort is a sorting algorithm that utilizes the principles of a Binary Heap data structure to sort elements within an array. The process begins by constructing a Max Heap or Min Heap from the unsorted array, ensuring that the root node holds the maximum (or minimum) value compared to its children in the Max Heap (or vice versa in a Min Heap).

In the next step, the algorithm performs heapify operations, involving reorganization of the heap after each element removal to maintain heap property. During the sorting phase, elements are sequentially removed from the heap, starting from the root node. After each removal, the remaining elements undergo heapify operations to preserve the heap structure. The removed elements are stored in the array, ultimately resulting in a sorted arrangement.

Heap Sort Algorithm Steps:

Convert the unsorted array into a Max Heap or Min Heap.
Perform heapify operations to maintain the heap property after each element removal.
Sequentially remove elements from the heap, starting from the root node. After each removal, reorganize the heap to maintain the heap property.
Store the removed elements in an array to obtain the sorted order.

Python Program for Heap Sort Algorithm.

Below is the code implementation of the Heap Sort Algorithm using Python language.

Python Code:

# Python Code implementatin for Heap Sort Algorithm
def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    left = 2 * i + 1  # Left child
    right = 2 * i + 2  # Right child

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

    # Check if right child exists and is greater than root
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 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 // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # Swap root with last element
        heapify(arr, i, 0)  # Heapify root element

# Example usage:
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("Sorted array:", arr)

Output:

Sorted array: [5, 6, 7, 11, 12, 13]

Time Complexity: The time complexity of Heap Sort in all cases is O(n log n). Building the heap takes O(n) time, and for each element, heapify takes O(log n) time. As there are n elements, the total time complexity is O(n log n).

Space Complexity: Heap Sort has a space complexity of O(1) as it performs sorting in place, utilizing the input array without requiring additional space.

Heap Sort Using Python Built-in Function.

In Python, the heapq module provides a heap sort functionality through the heapify() and heappop() functions. These functions enable Heap Sort by creating a min-heap and extracting elements one by one, resulting in a sorted list.

Main functions of heapq module:

heapify(iterable): Converts a given iterable (such as a list) into a heap in place. The function rearranges the elements so that they satisfy the heap property.

heappush(heap, item): Adds an element item to the heap while maintaining the heap property.

heappop(heap): Removes and returns the smallest element (root) from the heap while maintaining the heap property.

Python Code:

# Heap Sort Algorithm using heapq module
import heapq

def heap_sort(arr):
    # Convert the input list into a min-heap
    heapq.heapify(arr)  

    sorted_list = []
    while arr:
    # Extract elements one by one 
       sorted_list.append(heapq.heappop(arr))  
    return sorted_list

# Example usage:
arr = [12, 11, 13, 5, 6, 7]
sorted_array = heap_sort(arr)
print("Sorted array:", sorted_array)

Output:

Sorted array: [5, 6, 7, 11, 12, 13]

Time Complexity: O(n log n)

Space Complexity: O(1)