有关堆的一些知识和代码

佚名 6年前 (2019-04-26) 随笔 705人围观抢沙发百度已收录

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

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。堆是非线性数据结构，相当于一维数组，有两个直接后继。堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。 (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2) 若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。

大佬博客

预备知识

堆排序

　　堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

堆

　　堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

ok，了解了这些定义。接下来，我们来看看堆排序的基本思想及基本步骤：

堆排序基本思想及步骤

　　堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

步骤一构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

　　a.假设给定无序序列结构如下

2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

4.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

此时，我们就将一个无需序列构造成了一个大顶堆。

步骤二将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

a.将堆顶元素9和末尾元素4进行交换

b.重新调整结构，使其继续满足堆定义

c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

再简单总结下堆排序的基本思路：

　　a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

　　b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

　　c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

大佬gh手写堆代码：

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>

using namespace std;
typedef long long int lli;
namespace my{
inline int lson(int rt){return rt<<1;}
inline int rson(int rt){return (rt<<1)+1;} 
inline int rt(int son){return son>>1;}
struct heap{
    //数据 
    lli data[100001];
    //记录节点个数 
    int cnt;
    //初始化 
    heap()
    {
        memset(data,0,sizeof(data));
        cnt=0;
    }
    inline int size(){return this->cnt;}
    inline void downdate(int p)
    {
        while ((p<<1)<=this->cnt)
        {
            int son;
            if (this->data[lson(p)]>=this->data[rson(p)])
                son=lson(p);
            else
                son=rson(p);
            if (this->data[p]>this->data[son])break;
            swap(this->data[p],this->data[son]);
            p=son;
        }
    }
    inline void update(int p)
    {
        while (p!=1)
        {
            if (this->data[rt(p)]>this->data[p])break;
            swap(this->data[rt(p)],this->data[p]);
            p=rt(p);
        }
    }
    inline void push(lli num)
    {
        this->data[++this->cnt]=num;
        this->update(this->cnt);
    }
    inline lli top(){return this->data[1];}
    inline void pop()
    {
        this->data[1]=this->data[this->cnt--];
        this->downdate(1);
    }
};
} 

int main()
{
    int n;
    my::heap _;
    cin>>n;
    for (register int i=1;i<=n;i++)
    {
        lli num;
        cin>>num;
        _.push(num);
    }
    for (register int i=1;i<=n;putchar(' '),i++)
    {
        cout<<_.top();
        _.pop();
    }
    return 0;
}

先来看一个堆的快排

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;
priority_queue<int,vector<int>,greater<int> >q;//从大到小排序
//priority_queue<int,vector<int>,less<int> >q;  从小到大排序
int main()
{
    int n;
    int data;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>data;
        q.push(data);
    }
    while (!q.empty())
    {
        cout<<q.top()<<' ';
        q.pop();
    }
    return 0;
}

P1090 合并果子

我们选择用堆做堆

由于要使得搬运的总重量最少，所以我们需要每次都合并最小的两个

我们用堆：

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
int n,ans=0;

int main()
{
    cin>>n;
    for (register int i=1;i<=n;i++)
    {
        int num;
        cin>>num;
        q.push(num);
    }
    while (q.size()>1)//当堆数不唯一时 
    {
        int a=q.top();q.pop();
        int b=q.top();q.pop();
        ans+=(a+b);//合并堆 
        q.push(a+b);
    }
    cout<<ans;
    return 0;
}

这个其实相当于sort：

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
int n,ans=0;
int data[10001];

int main()
{
    cin>>n;
    for (register int i=1;i<=n;i++)
    {
        cin>>data[i];
    }
    for (register int i=1;i<=n-1;i++)
    {
        sort(data+i,data+1+n);
        ans+=data[i]+data[i+1];
        data[i+1]=data[i]+data[i+1];
    }
    cout<<ans;
    return 0;
}