---

📘 Heap Sort (with Running Time Analysis)

1️⃣ Introduction

Heap Sort is an efficient comparison-based sorting algorithm based on the Binary Heap data structure.

🔹 Idea

• Convert the array into a Max Heap
• The largest element is at the root
• Swap root with last element
• Reduce heap size and repeat

It combines the benefits of selection sort + heap structure.

---

2️⃣ What is a Heap?

🔹 Binary Heap

A complete binary tree satisfying:

• Max Heap → Parent ≥ Children
• Min Heap → Parent ≤ Children

📌 Heap is usually represented using an array

---

3️⃣ Working Principle

🔹 Steps

1. Build a Max Heap from the array
2. Swap root (largest) with last element
3. Reduce heap size
4. Apply heapify to restore heap
5. Repeat until sorted

---

4️⃣ Algorithm (Heap Sort)

🔹 Pseudocode

HeapSort(A, n):
   buildMaxHeap(A, n)

   for i = n-1 down to 1:
       swap A[0] and A[i]
       heapify(A, 0, i)

---

🔹 Heapify Function

heapify(A, i, n):
   largest = i
   left = 2*i + 1
   right = 2*i + 2

   if left < n and A[left] > A[largest]:
       largest = left

   if right < n and A[right] > A[largest]:
       largest = right

   if largest != i:
       swap A[i] and A[largest]
       heapify(A, largest, n)

---

5️⃣ Example (Step-by-Step)

🔹 Given Array:

A = [4, 10, 3, 5, 1]

---

🔹 Step 1: Build Max Heap

[10, 5, 3, 4, 1]

---

🔹 Step 2: Swap root with last

[1, 5, 3, 4, 10]

Heapify:

[5, 4, 3, 1, 10]

---

🔹 Step 3: Repeat

[4, 1, 3, 5, 10]
→ [3, 1, 4, 5, 10]
→ [1, 3, 4, 5, 10]

✔ Final Sorted Array:

[1, 3, 4, 5, 10]

---

6️⃣ Running Time Analysis

🔹 Step 1: Build Heap

• Time = O(n)

🔹 Step 2: Heapify for each element

• Heapify takes O(log n)
• Done n times

[
Total = O(n \log n)
]

---

7️⃣ Time Complexity

Case	Complexity
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n log n)

✔ Same in all cases

---

8️⃣ Space Complexity

• O(1) (in-place)
• No extra memory required

---

9️⃣ Recursion Tree Insight

• Height of heap = log n
• Each heapify operation = log n
• Repeated n times → n log n

---

🔟 Characteristics of Heap Sort

✔ In-place sorting
✔ Not stable
✔ Uses heap data structure
✔ Guaranteed O(n log n)

---

1️⃣1️⃣ Advantages

• No extra memory required
• Guaranteed performance
• Suitable for large datasets
• Better than O(n²) algorithms

---

1️⃣2️⃣ Disadvantages

• Not stable
• Slower than Quick Sort in practice
• More complex implementation

---

1️⃣3️⃣ Comparison with Other Sorting Algorithms

Algorithm	Time Complexity	Space
Heap Sort	O(n log n)	O(1)
Quick Sort	O(n log n) avg	O(log n)
Merge Sort	O(n log n)	O(n)

---

🔚 Conclusion

Heap Sort is a powerful and efficient sorting algorithm that guarantees O(n log n) performance with no extra memory.

It uses the heap data structure to repeatedly extract the maximum element.

---

📌 Exam Tip

👉 Always include:

• Heap definition
• Heapify process
• Time complexity
• Example

---