c++ 堆和堆排序

什么是堆(Heap)?

堆（Heap）是一种基于完全二叉树的数据结构，用于快速查找最大值或最小值。它满足以下性质：

完全二叉树：每一层从左到右填满，除了最后一层可以不完全填满，但节点必须靠左排列。
堆序性质：堆分为两种常见类型：
- 大顶堆（Max-Heap）：每个节点的值 ≥ 其子节点的值。根节点是最大值。
- 小顶堆（Min-Heap）：每个节点的值 ≤ 其子节点的值。根节点是最小值。

示例

大顶堆：

      10/  \5    3/ \2   1

小顶堆：

      1/ \3   2/ \5   4

堆的存储方式

数组存储：堆通常用数组表示，因为它是完全二叉树，利用数组的结构可以高效定位父节点和子节点。

父节点索引：parent(i) = (i - 1) / 2
左子节点索引：left(i) = 2 * i + 1
右子节点索引：right(i) = 2 * i + 2

数组表示例：

大顶堆 [10, 5, 3, 2, 1] 对应的结构为：

        10/  \5    3/ \2   1

堆的基本操作

插入元素

将新元素插入到数组末尾，然后向上调整堆（上滤），确保堆序性质。

算法：

将元素插入数组末尾。
通过“上滤”操作，将其逐层与父节点比较，必要时交换。

时间复杂度：O(log n)

删除堆顶元素

删除堆顶元素后，将最后一个元素移到堆顶，然后向下调整（下滤）。

算法：

删除堆顶元素，将最后一个元素放到堆顶。
通过“下滤”操作，将其逐层与子节点比较，必要时交换。

时间复杂度：O(log n)

构建堆

从无序数组构建堆，可以通过heapify（堆化）操作实现。
从最后一个非叶子节点开始，逐步向上调整。

时间复杂度：O(n)

堆实现(c++)

#include <iostream>
#include <vector>
using namespace std;// 调整为大顶堆
void heapify(vector<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 buildHeap(vector<int>& arr) {int n = arr.size();for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}
}// 打印数组
void printArray(const vector<int>& arr) {for (int i : arr) {cout << i << " ";}cout << endl;
}int main() {vector<int> arr = {4, 10, 3, 5, 1};cout << "原数组: ";printArray(arr);buildHeap(arr);cout << "构建大顶堆: ";printArray(arr);return 0;
}

堆排序（Heap Sort）

堆排序是基于大顶堆的排序算法。其过程如下：

将数组构建为大顶堆。
将堆顶元素（最大值）与末尾元素交换，并缩小堆的范围。
对剩余部分重新进行堆调整，直到所有元素有序。

堆排序代码：

#include <iostream>
#include <vector>
using namespace std;// 调整为大顶堆
void heapify(vector<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 heapSort(vector<int>& arr) {int n = arr.size();// 构建大顶堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 一个一个将最大值移到末尾，并调整剩余部分for (int i = n - 1; i > 0; i--) {swap(arr[0], arr[i]);  // 将当前最大值（堆顶）放到数组末尾heapify(arr, i, 0);    // 调整剩余部分为大顶堆}
}// 打印数组
void printArray(const vector<int>& arr) {for (int num : arr) {cout << num << " ";}cout << endl;
}int main() {vector<int> arr = {12, 11, 13, 5, 6, 7};cout << "排序前的数组: ";printArray(arr);heapSort(arr);cout << "排序后的数组: ";printArray(arr);return 0;
}

代码分析

heapify 函数：
这是一个递归函数，用于调整部分数组为大顶堆。在构建和排序过程中都需要用它来维护堆的性质。
heapSort 函数：
- 第一步：从最后一个非叶子节点开始，依次构建大顶堆。
- 第二步：逐次将堆顶（最大值）与末尾元素交换，并对剩余部分进行堆调整。
printArray 函数：
打印数组内容，帮助查看排序结果。