Heap Sort

Description
Heap sort is a sorting algorithm based on a binary heap (usually a max-heap or min-heap). Its core idea is to construct the sequence to be sorted into a heap, then repeatedly swap the heap's top element (maximum or minimum value) with the element at the end of the heap, and readjust the heap until the entire sequence is ordered. The time complexity of heap sort is O(n log n), and it is an in-place sort (requiring no extra space).

Knowledge Breakdown and Steps

1. Basic Concept of a Heap

   • A heap is a complete binary tree, meaning all levels except possibly the last are fully filled, and nodes in the last level are arranged from left to right.
   • Max-heap: The value of each node is greater than or equal to the values of its left and right child nodes (the root has the maximum value).
   • Min-heap: The value of each node is less than or equal to the values of its left and right child nodes (the root has the minimum value).

2. Heap Storage

   • A heap is typically stored in an array. For a node at index i in the array:
     • Parent node index: (i-1)/2 (floor division)
     • Left child node index: 2*i + 1
     • Right child node index: 2*i + 2

3. Steps of Heap Sort
   Step 1: Build the initial max-heap

   • Starting from the last non-leaf node (index n/2 - 1), perform a sink-down operation (heapify) on each node from right to left, bottom-up, so that the subtree rooted at that node satisfies the max-heap property.
   • Sink-down operation: Compare the current node with its left and right children. If a child has a larger value, swap the current node with the largest child, and continue adjusting downwards until the heap property is satisfied.

   Example (array [3, 5, 2, 7, 1]):

   • Non-leaf nodes are at index 1 (value 5) and index 0 (value 3).
   • Adjust index 1: Child node value is 1, no swap needed.
   • Adjust index 0: Left child value 5 < right child value 7, swap with right child, resulting in [7, 5, 2, 3, 1].

   Step 2: Sorting

   • Swap the heap's top element (maximum value) with the last element. Now the last element holds the maximum value.
   • Exclude the last element, and readjust the remaining heap (size reduced by 1) into a max-heap.
   • Repeat the above process until the heap size is 1.

   Continuing the example:

   • Initial heap [7, 5, 2, 3, 1], swap top 7 with last 1, get [1, 5, 2, 3, 7], adjust the first 4 elements into a new heap [5, 3, 2, 1].
   • Swap top 5 with last 1 (of the current heap), get [1, 3, 2, 5, 7], adjust the first 3 elements to [3, 1, 2].
   • Continue similarly, finally obtaining the sorted array [1, 2, 3, 5, 7].

4. Time Complexity Analysis

   • Heap construction process: O(n)
   • Each sink-down adjustment: O(log n)
   • Total n-1 adjustments: O(n log n)
   • Total time complexity: O(n log n)

Key Points Summary

• Heap sort uses the sink-down operation to maintain the heap property, gradually moving the maximum value to the end.
• Suitable for sorting large-scale data and requires no extra space (better than merge sort in this aspect).
• Unstable sort (equal values may change order).