堆排序

堆排序（Heap Sort）

---

1. 堆排序的基本原理

堆排序（Heap Sort）是一种基于二叉堆（Binary Heap）结构的排序算法，属于选择排序的一种改进版本。
其核心思想是利用最大堆或最小堆的性质，使得排序过程更加高效。

堆排序的具体步骤如下：

1. 构建最大堆

   （Build Max Heap）：

   • 先将无序数组调整为最大堆（即父节点大于等于子节点）。

2. 排序过程

   ：

   • 取出堆顶元素（最大值），放到数组末尾。
   • 重新调整剩余元素为最大堆，重复此步骤，直到所有元素排序完成。

---

2. 堆的基本操作

(1) 最大堆调整（Heapify）

• 保持堆的性质，即：父节点的值必须大于或等于子节点的值。
• 如果当前父节点不符合堆的性质，就和较大的子节点交换，并递归调整子树。

(2) 构建最大堆

• 从最后一个非叶子节点开始，对所有父节点执行 heapify 操作，使整个数组变成最大堆。

(3) 取出堆顶元素（排序）

• 交换堆顶元素和数组末尾元素，然后缩小堆的范围，再执行 heapify 操作。

---

3. 代码实现

#include <iostream>

using namespace std;

// **最大堆调整（保持堆的性质）**
void heapify(int arr[], int n, int i) {
    int largest = i;  // 设当前父节点为最大值
    int left = 2 * i + 1;  // 左子节点
    int right = 2 * i + 2; // 右子节点

    // **如果左子节点更大，则更新最大值索引**
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // **如果右子节点更大，则更新最大值索引**
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // **如果最大值索引不是当前父节点，则交换，并递归调整**
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);  // 递归调整子树
    }
}

// **构建最大堆**
void buildMaxHeap(int arr[], int n) {
    // **从最后一个非叶子节点开始**
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

// **堆排序**
void heapSort(int arr[], int n) {
    buildMaxHeap(arr, n);  // **1. 先构建最大堆**

    // **2. 依次取出堆顶元素，并调整堆**
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);  // **交换堆顶（最大值）和末尾元素**
        heapify(arr, i, 0);     // **调整剩余元素为最大堆**
    }
}

// **测试代码**
int main() {
    int arr[] = {4, 10, 3, 5, 1, 8, 6};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前：";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    cout << endl;

    heapSort(arr, size);  // 执行堆排序

    cout << "排序后：";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

---

4. 代码解析

(1) heapify()

• 该函数用于调整最大堆：
  • 先假设当前父节点最大，然后比较左右子节点。
  • 若子节点更大，则更新最大值索引，然后交换父子节点。
  • 递归调用 heapify()，直到满足最大堆性质。

(2) buildMaxHeap()

• 构建最大堆

  ：

  • 从最后一个非叶子节点（n/2 - 1）开始，依次执行 heapify()，确保父节点都大于子节点。

(3) heapSort()

• 先构建最大堆

  ，然后

  依次取出最大值

  ：

  • 交换堆顶元素（最大值）与数组末尾元素。
  • 缩小堆的范围，然后执行 heapify() 重新调整堆结构。

---

5. 时间复杂度分析

(1) 构建最大堆

• buildMaxHeap() 执行 heapify() n/2 次，每次 heapify 最多需要 O(log n) 时间。
• 总复杂度：O(n log n)

(2) 排序过程

• 每次取出堆顶元素（O(1)），然后调整堆（O(log n)），执行 n-1 次。
• 总复杂度：O(n log n)

(3) 总时间复杂度

• 堆排序的时间复杂度始终是 O(n log n)，比冒泡、选择、插入排序（O(n²)）高效。

---

6. 堆排序的特点

✅ 时间复杂度 O(n log n)，适用于大规模数据排序。
✅ 不稳定排序（因为交换操作可能破坏原有顺序）。
✅ 适用于对海量数据进行排序（如磁盘排序、日志数据排序）。
✅ *空间复杂度 O(1)*，属于**原地排序算法（不像归并排序 O(n) 需要额外存储）。

---

7. 总结

• 堆排序是一种基于完全二叉堆的数据结构，能够以 O(n log n) 的时间复杂度进行排序。
• 利用最大堆性质，每次取出堆顶元素（最大值）放到数组末尾，调整堆结构，最终实现排序。
• 相比快速排序（快排），堆排序的优势在于 最坏情况下依然是 O(n log n) 的时间复杂度，但缺点是交换操作较多，导致常数时间较大，实际性能不如快排。