heap_sort_demo

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# Filename: heap_sort_demo.py
# Version: 1.0.0
# Author: Jeoi Reqi

"""
Description:
    This script demonstrates the Heap Sort algorithm by sorting an array of integers.

Requirements:
    - Python 3.x

Functions:
    - heap_sort(arr):
        Perform heap sort on the given list `arr`.

Usage:
    - Run the script to see the Heap Sort algorithm in action.

Example:

                :: HEAP SORTING DEMO ::

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

        Heap Sorting Complete!

            Exiting Program...   GoodBye!

Additional Notes:
    - Heap Sort is an efficient sorting algorithm with a time complexity of O(n log n).
"""

def heap_sort(arr):
    """
    Perform heap sort on the given list `arr`.

    Args:
        arr (list): List of integers to be sorted in place.

    Returns:
        None. The list `arr` is sorted in place using heap sort.
    """
    def heapify(arr, n, i):
        largest = i
        l = 2 * i + 1
        r = 2 * i + 2

        if l < n and arr[largest] < 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)

    n = len(arr)

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

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

def main():
    """
    Main function to demonstrate heap sort.

    It initializes an example array, sorts it using heap_sort function,
    and prints the original and sorted arrays.
    """
    print("\n\t\t:: HEAP SORTING DEMO ::\n")

    # Example array to sort
    arr = [12, 11, 13, 5, 6, 7]

    # Print the original array
    original_arr_str = "["
    for index, num in enumerate(arr):
        if index == 0:
            original_arr_str += f"{num:2}"  # Add one space for single-digit numbers
        else:
            original_arr_str += f", {num:2}"  # Add one space for single-digit numbers
    original_arr_str += "]"
    print("Original array:", original_arr_str)

    # Sort the array using heap sort
    heap_sort(arr)

    # Print the sorted array
    sorted_arr_str = "["
    for index, num in enumerate(arr):
        if index == 0:
            sorted_arr_str += f"{num:2}"  # Add one space for single-digit numbers
        else:
            sorted_arr_str += f", {num:2}"  # Add one space for single-digit numbers
    sorted_arr_str += "]"
    print("Sorted array:  ", sorted_arr_str)

    # Print completion message
    print("\nHeap Sorting Complete!\n\n\tExiting Program...   GoodBye!")

if __name__ == "__main__":
    main()