Heap Sort

 Heap Sort

What is Heap Sort?
Heap Sort is a way to arrange numbers in order by first turning the list into a heap (a special tree-like structure), and then repeatedly removing the largest (or smallest) number to build the sorted list.

What is a Heap?
A heap is a tree where:

• The biggest number (in a max-heap) or the smallest number (in a min-heap) is at the top.
• Each "parent" node is bigger (or smaller) than its "children."

How does Heap Sort work?

• Step 1: Build a max-heap (largest number at the top).
• Step 2: Take the largest number (at the top of the heap) and put it at the end of the list.
• Step 3: Adjust the heap to make it a max-heap again.
• Step 4: Repeat until all numbers are sorted.

Step-by-step process:
List: [4, 10, 3, 5, 1]

• Step 1: Build a max-heap
  Heap: [10, 5, 3, 4, 1]

• Step 2: Swap the largest number with the last number
  → [1, 5, 3, 4, 10] (10 is sorted).

• Step 3: Adjust the heap (to rebuild the max-heap)
  → [5, 4, 3, 1, 10]

• Step 4: Swap again
  → [1, 4, 3, 5, 10] (5 is sorted).

• Repeat until the list is sorted:
  → [1, 3, 4, 5, 10]

Key idea:

• Use a heap to repeatedly find the biggest number and move it to the sorted part of the list.