堆其及应用

阿毛mao

2025-12-21 18:44:21

发布于：广东

5阅读

0回复

0点赞

堆（Heap）是计算机科学中的一种特殊数据结构，本质为基于完全二叉树的顺序存储数组，通常作为优先级队列使用。
其核心特性为父节点值始终不小于（最大堆）或不大于（最小堆）子节点值，物理存储采用数组实现，通过索引公式计算父子节点位置，例如父节点为(i-1)/2，左子节点为2i+1。
堆的实现通过向上调整（插入元素）和向下调整（删除元素）算法维护结构特性，建堆时间复杂度为O(n)，插入与删除操作复杂度为O(log n)。
堆排序通过原地堆化实现，时间复杂度为O(n log n)，TopK问题通过维护固定容量堆可将时间复杂度优化至O(n log k)。
常见应用包括优先队列、排序算法及图算法优化，标准模板库（STL）和多种编程语言均内置堆操作接口。

释义
堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。
堆总是满足下列性质：

值总是不大于或不小于其父结点的值
堆总是一棵完全二叉树

将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。
常见的堆有二叉堆、斐波那契堆等。
堆的物理结构本质上是顺序存储的，是线性的。
但在逻辑上不是线性的，是完全二叉树的这种逻辑储存结构。
堆的这个数据结构，里面的成员包括一维数组，数组的容量，数组元素的个数，有两个直接后继。
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。

若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。
由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。

STL
堆的STL包含于<algorithm>头文件中。
堆的STL支持以下的基本操作:

make_heap(first, last, comp);

建立一个空堆；
向堆中插入一个新元素；

top_heap(first, ast, comp);

获取当前堆顶元素的值；

sort_heap(first, last, comp);

对当前堆进行排序；

算法思想
不必将值一个个地插入堆中，通过交换形成堆。假设一个小根堆的左、右子树都已是堆，并且根的元素名为，其左右子结点为和，这种情况下，有两种可能：

1
2	此时应与两个子女中值较小的一个交换，结果得到一个堆，除非仍然大于其新子女的一个或全部的两个。

这种情况下，我们只需简单地继续这种将 “拉下来”的过程，直至到达某一个层使它小于它的子女，或者它成了叶结点。

筛选法

首先将要排序的所有关键码放到一棵完全二叉树的各个结点中（这时的完全二叉树并不具备堆的特性）。
显然，所有的结点都没有子女结点，因此以这样的为根的子树已经是堆，然后从的结点Ki开始，逐步把以为根的子树排成堆，直到以K0为根的子树排成堆，就完成了建堆过程。

在考虑将以为根的子树排成堆时，以为根的子树已经是堆，所以这时如果有和，则不必改变任何结点的位置，以为根的子树就已经是堆；否则就要适当调整子树中结点的位置以满足堆的定义。
由于Ki的左、右子树都已经是堆，根结点是堆中最小的结点，所以调整后的值必定是原来和中较小的一个。
假设较小，将与交换位置，这样调整后，并且以为根的子树原来已经是堆，不必再作任何调整，只有以为根的子树由于的值已经发生变化（与交换了），所以有可能不满足堆的定义（当的左、右子树已经是堆）。
这时可重复上述过程，考虑将以为根的子树排成堆。
如此一层一层递推下去，最多可以一直进行到树叶。
由于每步都保证将子树中最小的结点交换到子树的根部，所以这个过程是不会反馈的。
它就像过筛一样，把最小的关键码一层一层选择出来。

建堆效率
n个结点的堆，高度d = log n。根为第0层，则第i层结点个数为2^i，考虑一个元素在堆中向下移动的距离，这种算法时间代价为O(n)
由于堆有log n层深，插入结点、删除普通元素和删除最小元素的平均时间代价和时间复杂度都是O(log n)。

代码实现

#include <iostream>
#include <vector>
using namespace std;

// 打印数组
void printArray(const vector<int>& arr, const string& tip = "") {
    if (!tip.empty()) cout << tip << ": ";
    for (int num : arr) cout << num << " ";
    cout << endl;
}

// 堆调整：将以i为根的子树调整为大根堆
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();
    if (n <= 1) return;

    // 构建初始大根堆
    for (int i = n / 2 - 1; i >= 0; --i) {
        heapify(arr, n, i);
    }

    // 交换堆顶与末尾元素，调整剩余堆
    for (int i = n - 1; i > 0; --i) {
        swap(arr, arr[i]);
        heapify(arr, i, 0);
    }
}

// 测试函数
int main() {
    vector<int> arr = {4, 10, 3, 5, 1};
    printArray(arr, "原始数组");
    heapSort(arr);
    printArray(arr, "排序结果");
    return 0;
}

代码说明：
1、实现了大根堆的构建和调整算法
2、包含完整堆排序流程：建堆→交换→调整
3、提供打印功能观察排序过程
4、时间复杂度O(n log n)，空间复杂度O(1)
5、支持任意整数数组排序
6、可直接运行测试用例验证功能
代码来源：deepseek

堆的应用场景

应用场景	堆的用法
‌堆排序	利用堆顶元素的最大值（或最小值）特性，通过建堆、交换堆顶与末尾元素、调整堆等步骤实现排序，时间复杂度为O(n log n)。
‌TopK问题	通过维护固定容量的堆（如大小为K的小根堆），遍历数据流并动态调整堆，可高效找出前K个最大或最小元素，时间复杂度为O(n log k)。
‌优先队列	堆是优先级队列的高效实现，支持插入（O(log n)）和删除堆顶元素（O(log n)）操作，适用于任务调度、合并有序文件等场景。
‌图算法优化	堆可用于Dijkstra最短路径算法和Prim最小生成树算法，通过优先队列快速访问当前最短边或节点。

堆通过其高效性和灵活性，在排序、搜索、调度等领域具有广泛应用。

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论