Heap Sort with examples in Python

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. A binary heap is a complete binary tree that satisfies the heap property, which states that the value of each node is greater than or equal to the value of its parent, with the maximum-value element at the root.

Here is an example of heap sort in Python:

def heapify(arr, n, i):
    # Find largest among root, left child and right child
    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

    # Swap and continue heapifying if root is not largest
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

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

    # Build 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)

# Test
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print(arr)  # Output: [5, 6, 7, 11, 12, 13]

In this example, the heapify function is used to maintain the heap property by repeatedly swapping the root element with the largest of its children until the heap property is satisfied. The heap_sort function uses heapify to build a max heap from the input array, and then repeatedly swaps the root element with the last element in the heap and “heapifies” the heap, reducing its size by one, until the heap is sorted.

There are a few limitations to the heap sort algorithm:

1. Heap sort has a time complexity of O(nlog(n)), which is slower than some other sorting algorithms, such as quicksort and mergesort, which have a time complexity of O(nlog(n)).
2. Heap sort is not a stable sort, meaning that the relative order of elements with equal values may be changed during the sort. This is because the heap property only requires that the value of each node is greater than or equal to the value of its parent, and does not consider the relative order of elements with equal values.
3. Heap sort requires additional space in order to build the heap. The space complexity of heap sort is O(n), meaning that it requires an additional array of size n to store the heap.
4. Heap sort is not suitable for sorting small lists or partially sorted lists, as the overhead of building the heap may outweigh the benefits of the sorting algorithm.

Here are a few examples of when heap sort might be used in real life:

1. Sorting a large database of customer records by last name or email address.
2. Sorting a large list of products by price or rating for display on an e-commerce website.
3. Sorting a list of jobs by priority or deadline in a job scheduler.
4. Sorting a list of scientific data by timestamp or measurement value.
5. Sorting a list of financial transactions by date or amount for record keeping.
6. Sorting a list of music tracks by title or artist for a music player.
7. Sorting a list of news articles by publication date or relevance for a news website.

Overall, heap sort is a useful algorithm for sorting large lists, but may not be the most efficient choice for all types of data or situations.