Heap Sort

---

Heap Sort is a comparison-based sorting algorithm that utilizes a binary heap data structure. It operates by first building a max-heap (or min-heap) from the input data, and then repeatedly extracting the maximum (or minimum) element from the heap and placing it into the sorted array. Heap Sort has an efficient time complexity of $O(n\log n)$ and is widely used due to its in-place sorting capability and relatively simple implementation.

---

What is Heap Sort?

Heap Sort is a sorting algorithm based on the binary heap data structure, which is a complete binary tree that satisfies the heap property. In a max-heap, the value of each node is greater than or equal to the values of its children, while in a min-heap, the value of each node is less than or equal to the values of its children.

Heap Sort works by:

1. Building a max-heap from the input data.
2. Extracting the root (maximum element) from the heap and placing it in the sorted array.
3. Rebuilding the heap after each extraction, until all elements are sorted.

Since heap operations such as insertion and deletion take $O(\log n)$ time, the overall time complexity of Heap Sort is $O(n\log n)$.

---

How Does Heap Sort Work?

Heap Sort works in two main phases:

Phase 1: Build a Max-Heap

1. Start by rearranging the input array into a binary heap. This is done by repeatedly applying the heap property to all non-leaf nodes of the binary tree, starting from the last non-leaf node and moving towards the root.
2. The result is a max-heap where the root contains the maximum element.

Phase 2: Sorting

1. Swap the root (maximum element) with the last element of the heap. This moves the largest element to its correct position in the sorted array.
2. After swapping, reduce the size of the heap by 1 (ignore the last element, as it is now sorted).
3. Restore the heap property by "heapifying" the root of the heap (this operation ensures the max-heap property is maintained).
4. Repeat the process until all elements are sorted.

---

Heap Sort: Python Code Implementation

Here is a Python implementation of Heap Sort:

# Function to heapify a subtree rooted at index i, assuming the subtrees are already heapified
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 larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left

    # Check if right child exists and is larger than the largest so far
    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)  # Recursively heapify the affected subtree

# Main function to implement Heap Sort
def heap_sort(arr):
    n = len(arr)

    # Build a max-heap by applying heapify starting from the last non-leaf node
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # One by one extract elements from the heap and place them in their correct position
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # Swap root (max element) with the last element
        heapify(arr, i, 0)  # Heapify the reduced heap

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

Output:

Unsorted Array: [12, 11, 13, 5, 6, 7]
Sorted Array: [5, 6, 7, 11, 12, 13]

Explanation of Code:

• Heapify: The heapify function ensures that a subtree rooted at a given index satisfies the heap property. If the subtree is not a valid heap, the function swaps elements to restore the heap property.
• Heap Sort: The heap_sort function first builds a max-heap from the input array and then extracts elements from the heap, placing them in the correct position by swapping the root with the last element. It then re-applies heapify to restore the heap property after each extraction.

---

Time and Space Complexity of Heap Sort

Time Complexity:

• Building the Max-Heap: Building the heap takes $O(n)$ time, as each heapify operation takes $O(\log n)$, and there are $n\mathrm{/}2$ nodes to heapify.
• Sorting the Array: Each extraction of the maximum element takes $O(\log n)$ time, and this is done $n$ times (one for each element). Hence, sorting takes $O(n\log n)$ time.
• Overall Time Complexity: The overall time complexity of Heap Sort is $O(n\log n)$, which holds for the best, average, and worst-case scenarios.

Space Complexity:

• Space Complexity: Heap Sort is an in-place sorting algorithm, meaning it does not require any extra space apart from the input array. Therefore, its space complexity is $O(1)$.

---

Advantages of Heap Sort

1. Efficient Sorting: Heap Sort provides a guaranteed time complexity of $O(n\log n)$, which is efficient compared to algorithms like Bubble Sort or Selection Sort (which have $O(n^2)$ time complexity).
2. In-place Sorting: Heap Sort does not require any additional memory beyond the input array, making it space-efficient ($O(1)$).
3. No Worst-Case Scenarios: Unlike algorithms such as QuickSort, which can degrade to $O(n^2)$ in the worst case, Heap Sort maintains a consistent $O(n\log n)$ performance.

---

Disadvantages of Heap Sort

1. Not Stable: Heap Sort is not a stable sorting algorithm, meaning that elements with the same value may not retain their relative order after sorting.
2. Slow Compared to QuickSort: While Heap Sort guarantees $O(n\log n)$ time complexity, it can be slower in practice compared to QuickSort due to the overhead of maintaining the heap structure.
3. Complex Implementation: The heapify process and the logic for maintaining the heap can be more complex to implement compared to simpler algorithms like Insertion Sort or Selection Sort.

---

When to Use Heap Sort?

1. When Space Efficiency is Important: Heap Sort is ideal when space is limited since it is an in-place sorting algorithm with $O(1)$ space complexity.
2. When You Need Guaranteed Performance: If you need a sorting algorithm with guaranteed $O(n\log n)$ time complexity, Heap Sort is a good choice, as it avoids the worst-case performance issues of algorithms like QuickSort.
3. In Priority Queues: Heap Sort is often used to implement priority queues, where the elements are dynamically added and removed, and you need to efficiently extract the maximum (or minimum) element.

---

---