---

📘 Heap Sort (HeapSort)

Heap Sort is a comparison-based, in-place, efficient sorting algorithm that uses a Binary Heap data structure.

It is based on the idea of:

1. Building a Max-Heap from the input array
2. Repeatedly removing the maximum element (root of heap)
3. Placing that element at the end of the array
4. Adjusting the heap again
5. Continue until array is sorted

---

📌 Binary Heap Used in Heap Sort

Heap Sort uses Max-Heap for sorting in ascending order.

Max-Heap Properties

• A complete binary tree
• Every node is greater than or equal to its children
• Root always contains the maximum element

Heap represented as array

For index i:

• left child = 2*i + 1
• right child = 2*i + 2
• parent = (i - 1)//2

---

📘 Steps of Heap Sort

Step 1: Build a Max-Heap

Convert the array into a max-heap by calling heapify() from bottom to top.

Step 2: Repeatedly swap and heapify

• Swap the first element (max) with the last element
• Reduce heap size
• Heapify the root again
• Continue until all elements are placed in correct position

---

📌 Time Complexity

Operation	Time
Building heap	O(n)
Each delete-max (n times)	O(log n)
Total Time	O(n log n)

---

📌 Space Complexity

• O(1) (in-place sorting)

---

📌 Characteristics

• In-place
• Not stable
• Guaranteed O(n log n) (better worst-case than QuickSort)
• Uses heap structure, not divide & conquer

---

📘 Python Code for Heap Sort

Below is clean and correct code using manual heap operations (no library):

def heapify(arr, n, i):
    largest = i          # Initialize largest as root
    left = 2 * i + 1     # Left child index
    right = 2 * i + 2    # Right child index

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

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

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


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

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

    # Step 2: Extract elements one by one
    for i in range(n - 1, 0, -1):
        # Move current root to end
        arr[i], arr[0] = arr[0], arr[i]

        # call max heapify on the reduced heap
        heapify(arr, i, 0)


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

---

📘 Example Output

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

---

📘 Summary (Exam Notes)

• Heap Sort uses Max-Heap to sort in ascending order
• Two steps: Build Heap + Repeated Extract Max
• Time: O(n log n) (always reliable)
• Space: O(1) (in-place)
• Not stable
• Better worst-case performance than QuickSort

---