堆火熠熠：燃烧吧，我们的数据结构之魂

“堆蕴秩序：堆排序的诗篇与画卷”

前置知识简要：堆

堆（heap）是一种满足特定条件的完全二叉树，主要可分为两种类型，如图 8-1 所示。

小顶堆（min heap）：任意节点的值 其子节点的值。
大顶堆（max heap）：任意节点的值 其子节点的值。

`/* 初始化堆 */
// 初始化小顶堆
priority_queue<int, vector<int>, greater<int>> minHeap;
// 初始化大顶堆
priority_queue<int, vector<int>, less<int>> maxHeap;

/* 元素入堆 */
maxHeap.push(1);
maxHeap.push(3);
maxHeap.push(2);
maxHeap.push(5);
maxHeap.push(4);

/* 获取堆顶元素 */
int peek = maxHeap.top(); // 5

/* 堆顶元素出堆 */
// 出堆元素会形成一个从大到小的序列
maxHeap.pop(); // 5
maxHeap.pop(); // 4
maxHeap.pop(); // 3
maxHeap.pop(); // 2
maxHeap.pop(); // 1

/* 获取堆大小 */
int size = maxHeap.size();

/* 判断堆是否为空 */
bool isEmpty = maxHeap.empty();

/* 输入列表并建堆 */
vector<int> input{1, 3, 2, 5, 4};
priority_queue<int, vector<int>, greater<int>> minHeap(input.begin(), input.end());`

堆的存储，以数组形式实现存储堆

堆的实现以及堆相关操作

堆的常见应用

• 优先队列：堆通常作为实现优先队列的首选数据结构，其入队和出队操作的时间复杂度均为 ，而建队操作为 ，这些操作都非常高效。
• 堆排序：给定一组数据，我们可以用它们建立一个堆，然后不断地执行元素出堆操作，从而得到有序数据。然而，我们通常会使用一种更优雅的方式实现堆排序。
• 获取最大的 个元素：这是一个经典的算法问题，同时也是一种典型应用，例如选择热度前 10 的新闻作为微博热搜，选取销量前 10
  的商品等。

阅读本节前，请确保已学完“堆“章节。

堆排序（heap sort）是一种基于堆数据结构实现的高效排序算法。我们可以利用已经学过的“建堆操作”和“元素出堆操作”实现堆排序

图解堆排序原理

以此循环直至

C++代码实现：

#include <vector>
#include <iostream>
#include <algorithm> // 引入 swap 函数

using namespace std;

// 向下调整堆
void siftDown(vector<int>& nums, int n, int i) {
    while (true) {
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma])
            ma = l;
        if (r < n && nums[r] > nums[ma])
            ma = r;
        if (ma == i) {
            break;
        }
        swap(nums[i], nums[ma]);
        i = ma;
    }
}

/* 堆排序 */
void heapSort(vector<int>& nums) {
    int n = nums.size();
    // 建堆操作
    for (int i = n / 2 - 1; i >= 0; --i) {
        siftDown(nums, n, i);
    }
    // 提取最大元素并重新建堆
    for (int i = n - 1; i > 0; --i) {
        swap(nums[0], nums[i]);
        siftDown(nums, i, 0);
    }
}

int main() {
    vector<int> nums = { 10, 30, 40, 20, 100 };
    cout << "Before sorting: ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    heapSort(nums);

    cout << "After sorting: ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

堆排序是

一种基于比较的排序算法

，它利用了堆这种数据结构——完全二叉树的一种特殊形式。堆通常分为两种类型：大顶堆（父节点的值大于或等于其子节点的值）和小顶堆（父节点的值小于或等于其子节点的值）。堆排序主要依赖于大顶堆实现降序排序，也可以通过小顶堆实现升序排序。

堆排序算法的步骤如下：

1. 建堆：

   • 从最后一个非叶子节点开始向上逐层构建堆，确保每一个子树都符合堆的性质。
   • 这个过程的时间复杂度通常是 O(n)，其中 n 是待排序元素的数量，因为每个非叶子节点都需要做一次下沉操作。

2. 堆排序过程：

   • 将堆顶元素（即当前的最大值或最小值，取决于大顶堆还是小顶堆）与堆尾元素交换位置，即将最大（或最小）元素放到正确的位置。
   • 然后将新的堆（不包括刚刚被交换出去的元素）重新调整为堆，再次使得堆顶元素是最值。
   • 重复以上步骤，每次都将堆顶元素移到已排序区，并重新调整堆，直到堆中只剩下一个元素。

3. 时间复杂度分析：

   • 建堆阶段：O(n)
   • 排序阶段：需要进行 n-1 次交换和调整，每次调整堆的时间复杂度为 O(logn)，因此总的时间复杂度为 O((n-1)logn) ≈ O(nlogn)。
   • 因此，堆排序的总体时间复杂度为 O(n) + O(nlogn) = O(nlogn)。

4. 空间复杂度分析：

   • 堆排序是原地排序算法，它仅需少量附加空间用于递归调用栈和临时存储，因此空间复杂度为 O(1)。

5. 稳定性：

   • 堆排序不是稳定的排序算法，即相等的元素可能会在排序后改变相对顺序。

6. 适用场合：

   • 堆排序适合处理大数据量且内存有限的情况，因其不需要额外的存储空间，同时具有较好的时间性能。尤其在需要频繁找出最大（或最小）元素的场合，例如优先队列中，堆结构非常有用。但针对较小规模或对稳定性要求高的数据排序，可能有更适合的选择，比如插入排序或归并排序。

top_k问题

1. 初始化一个小顶堆，其堆顶元素最小
2. 先将数组的前 个元素依次入堆。
3. 从第 个元素开始，若当前元素大于堆顶元素，则将堆顶元素出堆，并将当前元素入堆。
4. 遍历完成后，堆中保存的就是最大的 个元素。

top_k图解

/*经典的top——k问题*/

#include <queue>
priority_queue<int, vector<int>, greater<int>> topheap(vector<int>& nums,int k) {
    priority_queue<int, vector<int>, greater<int>> heap;/*create a heap*/
    for (int i = 0; i < k; i++) {
        heap.push(nums[i]);/*将k个元素入堆*/
    }
    for (int i = k; i < nums.size(); i++) {
        if (nums[i] > heap.top()) {
            /*如果当前元素大于堆顶元素*/
            heap.pop();
            heap.push(nums[i]);
        }
    }
    return heap;
}   

int main() {
    vector<int> nums = { 10, 30, 40, 20, 100 };
    cout << "Before sorting: ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    heapSort(nums);

    cout << "After sorting: ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    cout << "*****************\n" << endl;
    priority_queue<int, vector<int>, greater<int>> maxKHeap = topheap(nums, 3);

    cout << "The largest " << 3 << " elements in the array are: ";
    while (!maxKHeap.empty()) {
        cout << maxKHeap.top() << " ";
        maxKHeap.pop();
    }
    cout << endl;

    return 0;
}

资源：堆排序算法