数据结构——堆

堆

1.数据结构

堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
$$
(k_i \le k_{2i} 且 k_i \le k_{2i+1})或者(k_i \ge k_{2i} 且 k_i \ge k_{2i+1}),(i = [1,\frac{n}{2}])
$$

• 最高效的优先级队列。可以被看作一棵完全二叉树（完全二叉树_百度百科 (baidu.com)）的数组对象。

• 堆中某个结点的值总是不大于或不小于其父结点的值。

• 根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

• 堆是非线性数据结构，相当于一维数组，有两个直接后继。堆通常用一维数组存储。假设某个节点（根节点除外）对应的一维数组下标为x(一维数组下标从1开始），则其父节点下标为x/2，左子节点下标为2x，右子节点下标为2x+1。

• 用数组实现堆时，堆为完全二叉树而不是非完全二叉树的本质是因为其数组的存储结构。

图解：

2.相关操作原理（以小根堆为例）

始终记住堆是一个完全二叉树且满足一个节点和其父节点两个子节点需满足的大小关系！

2.1堆的插入

当一个新元素想要插入这个堆的时候，我们首先把他放到这个堆的末尾（放到末尾可以满足完全二叉树的特性）。然后依据堆的特性，对它的位置进行调整（不断上浮），直至满足堆的条件。

2.2堆中元素的删除

一般是删除堆顶元素，将数组末尾的元素拿到堆顶空缺的位置，然后对其进行下沉操作。若要求删除非堆顶元素，则将该元素（1）首先和堆顶元素（2）进行置换，再删除（2），将堆尾元素（3）补充到堆顶，然后堆元素（1）和元素（3）进行位置调整。

2.3小根堆的建立

堆的建立即为“堆的插入”的应用。将元素不断放到堆的末尾，然后进行位置调整。

3.代码实现（以小根堆为例）

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

void heap_swap(int a, int b) {// 交换两个点，及其映射关系
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u) {//把一个节点不断 下沉 使其存储在合适位置
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;//h[u]比其左儿子小,t为其左儿子
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;//若右儿子比左儿子小,则t为其右儿子
    if (u != t) {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u) {//把一个节点不断 上浮 使其存储在合适位置
    while (u / 2 && h[u] < h[u / 2]) {
        heap_swap(u, u / 2);
        u >>= 1;	//u除以2的快速实现
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);//从最后一个节点的父节点开始，i--从后往前对所有节点进行下沉

4.对建堆代码for (int i = n / 2; i; i -- ) down(i);的思考

1. 该代码的意义和形象理解是什么？

   • 从最后一个有儿子节点的父节点向前遍历，依次让每个结点找到其合适的位置

2. 除了这种建堆方式，还有什么别的建堆方式？

   • ①从最后一个非叶子节点开始，逐个向前进行下沉操作来实现
   • ②从第一个非叶子节点开始，逐个向后进行上浮操作来实现

3. 为什么down()操作必须满足左右子树均为堆？

   • 如果一个节点的左右子树不满足堆的性质，那么下沉操作可能导致破坏堆的性质

4. 为什么要从i = n / 2往上建堆？

   • 只需要对索引小于等于 n / 2 的节点进行下沉操作，即从最后一个非叶子节点开始（最后一个有儿子节点的父节点），逐个向前处理每个非叶子节点，直到根节点。

5. 为什么不从 i = 1 开始到 i == n，将每一个节点挨个插入的方式建堆？

   • 如果采用从 i = 1 开始到 i == n 的方式，将每个节点逐个插入堆中，那么建堆的时间复杂度将变为 O(nlogn)，而不是 O(n)。

     因为插入操作的时间复杂度是 O(logn)。当我们将一个元素插入到堆中时，需要将其放置在堆的末尾，然后进行上浮操作，将其与父节点进行比较和交换，直到满足堆的性质。在最坏情况下，新插入的元素需要上浮到堆的根节点位置，这需要进行 O(logn) 次比较和交换操作。

     如果我们按顺序逐个插入所有的节点，则第一个插入的节点需要进行 O(logn) 次操作，第二个插入的节点需要进行 O(logn-1) 次操作，以此类推。总的时间复杂度为：O(logn) + O(logn-1) + O(logn-2) + ... + O(1) = O(logn + log(n-1) + log(n-2) + ... + log(1))，个和式的结果是 O(logn!)，即 O(nlogn)。

     相比之下，从 i = n / 2 开始进行下沉操作的方式可以在 O(n) 的时间内建立堆。

6. 为什么不直接使用sort()操作建堆（令sort()操作满足数组元素从小到大排列或从大到小排列，对存储堆元素的数组直接排序）？

   • sort() 函数通常使用的是比较排序算法，例如快速排序、归并排序、堆排序等。这些排序算法的时间复杂度通常为O(nlogn)，大于该操作的时间复杂度O(n)；
   • sort()操作满足从小到大排列或从大到小排列后，生成的结果是完全单调的。而堆并不需要满足完全单调的性质，只需要确保父节点和子节点的相对大小关系即可。

7. 该操作（for (int i = n / 2; i; i -- ) down(i);）建堆的时间复杂度为什么是o(n)的？

   • 

8. 该操作直接满足了节点与其子节点之间的相对大小关系，而不是整个数组都是从小到大排序的，那堆排序是如何实现的？

   • （转自Chat-GPT 3.5）

     堆排序是一种基于堆数据结构的排序算法。它的主要思想是将待排序的数组构建为一个最大堆（或最小堆），然后不断地取出堆顶元素，将其与堆的最后一个元素交换，再对剩余的元素进行堆调整，重复这个过程直到整个数组有序。

     下面是堆排序的步骤：

     1. 建堆：将待排序的数组构建为一个最大堆（或最小堆），这可以通过从最后一个非叶子节点开始，逐个向前进行下沉操作来实现。或者，也可以从第一个非叶子节点开始，逐个向后进行上浮操作来实现。

     2. 排序：将堆顶元素与堆的最后一个元素交换，即将最大（或最小）元素放到数组的末尾。然后，对剩余的元素进行堆调整，以维护堆的性质。

     3. 重复步骤 2，直到整个数组有序。每次交换堆顶元素和堆的最后一个元素后，堆的大小减小 1。

     堆排序的作用是对数组进行原地(in-place)排序，具有稳定的时间复杂度 O(nlogn)。堆排序相比于其他排序算法的一个优点是，它不需要额外的空间来存储临时数据，因此空间复杂度是 O(1)。另外，堆排序的最坏、平均和最好情况下的时间复杂度都是 O(nlogn)，因此在大多数情况下具有较好的性能。

     堆排序的另一个重要应用是在优先队列中，用于高效地维护具有优先级的元素集合。通过使用堆数据结构，可以实现高效的插入、删除和查找操作。

5.例题

原题链接：838. 堆排序 - AcWing题库

这个题很有学习价值。由于这代题目时间复杂度卡的比较死，所以思路一共经历了如下的三个过程

• 过程一：很粗暴的堆排序，先构造大根堆得到堆顶的最大元素，再将最大元素固定到数组末尾，并对剩下的元素（未固定的元素）再求大根堆，以此模式依次将每一轮的最大元素依次固定到数组的末端，最后得到严格的从小到大的数组。

#include 
#include 
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n, m;

void down(int x) {//构造大根堆的down,堆顶为最大元素
    int t = x;//t是要交换到的位置，且保证一个节点的左节点比右节点小
    
    if (x*2 <= n && a[2*x] > a[t])  t = 2*x;
    if (x*2+1 <= n && a[2*x+1] > a[t])  t = 2*x+1;
    
    if (t>x) {
        swap(a[x],a[t]);
        down(t);
    }
}

int main () {
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i ++ ) cin >> a[i];
    
    while (n) {
        for (int i = n/2 ; i>=1 ; i -- ) down(i);//构造大根堆
        swap(a[n], a[1]);//再将大根堆堆顶的元素（最大值）固定到数组末尾
        n--;//再对没有固定的元素再构造大根堆
    }
    
    for (int i = 1 ; i <= m ; i++)   cout << a[i] << ' ';
    return 0;
}

• 过程二：过程一的小优化，从n次的整体建大根堆过程变成m次的整体建小根堆过程，减少了(n-m)次整体建堆的过程

while (m--) {
    for (int i = n/2 ; i>=1 ; i -- ) down(i);//先构造小根堆
    printf("%d ",a[1]);//输出小根堆堆顶元素
    swap(a[n], a[1]);//再将小根堆堆顶的元素（最小值）固定到数组末尾
    n--;//再对没有固定的元素再构造小根堆
}

• 过程三：不再完整的建立大根堆或者小根堆，而是采用部分建堆，建立一次小根堆之后，输出小根堆堆顶元素，再将小根堆堆顶元素固定到数组末尾，再对置换到堆顶的原数组末尾元素进行down()操作就能每次在堆顶得到一个最小元素

while (m--) {
    printf("%d ",a[1]);//输出小根堆堆顶元素
    swap(a[n], a[1]);//再将小根堆堆顶的元素（最小值）固定到数组末尾
    n--;
    down(1);//没有整体进行down()操作，而不是采用循环整体建堆
}