前言

大前天(2019/1/19)作者回到机房,发现自己咕咕咕半个月后被学长嘲讽了,于是去找Herself32学堆……


初始约定

在下文堆的STL实现中,很多时候会出现(begin , end)

这表示一段数组上的区间:从begin 到 end

其中,begin为开头,end为结尾。

就像下图:

5jEGTp.png

但值得一提的是,begin在这个区间内,但end不在


何为堆?

堆(英语:heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。
——百度百科

……

度娘越来越坏了,只会装高冷。还是看看通俗易懂的解释吧。

事实上,堆就是一颗完全二叉树,但它还要满足一个条件:

  • 堆中的每个节点不论怎么调整,都不小于(或不大于)它的父节点。

根据这个条件,我们就可以把堆分成两种:大根堆小根堆

就像下图,就是两个典型的小根堆和大根堆:

小根堆:
5jZPT9.jpg

大根堆:
5jZvSu.jpg

怎么样,是不是很懵逼?

那是因为我忘了告诉你小根堆和大根堆的定义了。

我们将根节点最大的堆叫做大根堆将根节点最小的堆叫做小根堆

但要注意:必须是每一颗子树都要满足条件,即每一颗子树的每一个节点都要比它的父节点大(或小)。

这是按根节点的大小来分,如果按操作种类来分,那么常见的堆有二叉堆、斐波那契堆等。


如何存储一个堆?

看到这,你可能要问了:“既然这样,怎么存储一个堆呐?”

别急,慢慢看就知道了。

我们知道,堆是一种线性的数据结构,有唯一的后继。

所以

开一维数组模拟啊

学过完全二叉树的同学都知道这样一句话:在完全二叉树中,一个节点的编号为x,则它的左儿子编号为2x, 右儿子编号为2x + 1。

在前面我已经说过,堆也是一颗完全二叉树。

因此,堆也满足这个性质。

如果我们定义一个名为Heap[]的数组表示堆,那么

  • (小根堆)。
  • (大根堆)。

同时,我们还可以看出,堆顶元素一定是最大(或最小)元素。


堆的操作。

现在你可能要问:“这么麻烦的堆,有什么用吗?”

当然是拿来怼人啦

咳咳,一个堆支持以下4种操作:

  • 插入一个节点
  • 删除堆顶元素
  • 输出堆顶元素
  • 堆排序

在讲这4种操作之前,我们先来看看堆的两种基本操作:Shiftup & Shiftdown
(ps.所有的操作都基于这两种基本操作)

Shiftup(ps.大根堆)

众所周知,大根堆中的每一个父节点都大于它的任意子节点

因此,我们在插入一个节点后需要把它与它的父节点比较

如果它比它的父节点大,则交换,继续比较。

否则,则退出循环。

刚不过就认怂呗

来看这个图:
5jh3Oa.jpg

此时,我们在树的最后插入一个元素36(ps.插入元素时要在树的最后插入):

5jZnJE.jpg

现在开始Shiftup, 此时36与他的父节点19比较,发现自己比他大,进行交换。

5jZoIQ.jpg

交换后的36与它的父节点26比较,发现自己比他大,进行交换。

5jZw52.jpg

最后36与90比较,发现比不过了,于是认怂,break掉循环,结束。

5jh5Uz.jpg

伪代码如下

    void Shiftup(int x){            //x为节点下标
        while(x不是根节点){
            if(Heap[x] 大于它的父节点){
                将Heap[x]与它的父节点交换;
                x = x / 2;          //父节点的下标为子节点下标除以2
            }
            else{
                break;
            }
        }
    }

Shiftdown (ps.大根堆)

同理,有上浮就会有下沉。可以把Shiftdown看成Shiftup的反过程。

唯一不同在于,Shiftdown有两个比较对象,分别是他的左儿子和右儿子。

在交换之前,需要先找到它的左儿子和右儿子中较大的那一个。

来看这个图:

5jPFcp.jpg

此时,我们删除堆顶的90,成了下面这个样子:

5jPJbA.jpg

最后一个元素会上来补位,就成了这样:

5jPqzh.jpg

现在,Shiftdown开始了。
先将36与17比较,发现36更大,于是把36与19交换,成了下图的样子:

5jadsy.jpg

再把25与26比较,发现26更大,于是把26与19交换,成了这样:

5jabEB.png

现在,19已经没有子节点了。于是我们可以break掉循环,结束Shiftdown

伪代码如下

    void shiftdown(int x){
        int maxn,number;
        while(Heap[x]有子结点){
            maxn = max(它的左子结点 , 它的右子结点);
            if(maxn == 左子结点){
                number = 左子结点的下标;
            }
            else if(maxn ==右子节点){
                number = 右子节点的下标; 
            }

            if(Heap[x] < a[number]){
                将Heap[x]与相对较小的子结点交换
                x = number;
            }
            else{
                break;
            }
        }
    }

(ps.至于插入和删除一个元素,自己想想也就知道了。在这里不再专门讲述)其实是作者太懒


输出堆顶元素

    cout << Heap[1];

不知道为啥的请回看[如何存储一个堆]部分。


堆排序

如果是升序排序,就建一个小根堆持续弹出。

降序就建一个大根堆持续弹出即可。


堆的STL

本部分仅适合c++选手食用,Pascal & C选手请自觉跳过.(怕你们怀疑自己选错语言)

众所周知,cpp为我们提供了一个很人性化的模板库——STL

那么……

堆在STL中有没有可以调用的模板呐?

答案是肯定的。

在STL中,堆有4种操作,分别为make_heap(); pop_heap(); push_heap(); sort_heap(); 它们都在algorithm库中

下面,我们就来深入研究一下这4种操作

make_heap

光通过字面应该也能理解,这个函数是用来建立一个堆的。

格式为make_heap(begin , end);

默认建立的是一个大根堆哦。

既然如此,如果要建立一个小根堆该怎么办呐?

写一个比较函数cmp不就行了!

就像下边

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

bool cmp (int a, int b){
    return a > b;
}

int n, a[10001];

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    make_heap(&a[1], &a[n], cmp);
    ……
    return 0;
}

一个小根堆就这么建成了QVQ

但一定注意,cmp是放在end后边的。


pop_heap

这个函数可以将堆中的堆顶元素弹出。

就好像前面的Shiftdown一样

格式为pop_heap(begin , end , cmp); (大根堆不加cmp)


push_heap

既然有弹出,那就一定会有加入

而这个函数就可以在堆中加入一个元素。

就像前面的Shiftup。

格式为push_heap(begin , end , cmp); (大根堆不加cmp)


sort_heap

显然,这是一个堆排序函数。

堆排序在实际排序时应用不多,但一些优化必须使用。

格式为sort_heap(begin , end , cmp); (大根堆不加cmp)

但值得一提的是,堆排之后,这个堆就不是一个合法的堆了


priority_queue

想必大家都已经学会队列了吧 没学过的请点击这里

现在我们要讲的就是队列的一种特殊形式:优先队列

那么,什么是优先队列呐?

学过队列的同学都知道,队列就像公平的队伍一样,从后面进,前面出,出队的顺序与节点的权值无关

优先队列,就像一个不太公平的队伍。总是让当前权值最大或最小的节点先出队

所以……

这不就是一个典型的堆嘛QAQ

但别忘了,优先队列也是队列,所以它的所有操作都包含在queue库中

优先队列的定义如下:

priority_queue<int > Q;   //定义一个名为Q的最大优先队列,队列里的数据类型为int型

但是,优先队列默认为最大优先队列,即大根堆。如果我们要定义一个最小优先队列,写法就会不同。

priority_queue<int , vector<int> , greater<int> > Q;    //定义一个名为Q的最小优先队列,数据类型为int

随带提一句,greater<int>后面一定要有一个空格</int>,否则的话会被编译器识别为右移运算符“>>”

现在,我们就来讲讲优先队列的几种操作。


push

无疑,这个函数可以把一个元素加入优先队列,和队列中的push用法一样。

代码如下:

priority_queue<int > Q;
int a;
Q.push(a);

top

这个函数可以获取队列中的最大或最小元素,即堆顶。但它并不会删除堆顶元素

代码如下:

priority_queue<int > Q;
int a = Q.top();

pop

这个函数可以弹出堆顶元素,即删除堆顶元素。

代码如下:

priority_queue<int > Q;
Q.pop();

empty

这个函数可以判断堆是否为空,返回值是一个bool型变量。

如果说队列为空,则返回true,否则返回false

代码如下:

priority_queue<int > Q;
bool a;
a = Q.empty;

附件:堆[手写模板]

代码描述:洛谷P3378.

源代码(ps.防作弊已开启):

#include<iostream>
using namespace std;
int n,x,len = 1,a[1000001],ans[1000001];

void shiftup(int x){
    while(x > 1){
        if(a[x] < a[x / 2]){
            swap(a[x] , a[x / 2]);
            x = x / 2;
        }
        else{
            break;
        }
    }
}

void shiftdown(int x){
    int minn,number;
    while(x * 2 + 1 <= len){
        minn = min(a[x * 2 + 1] , a[x * 2]);
        if(minn == a[x * 2 + 1]){
            number = x * 2 + 1;
        }
        else if(minn == a[x * 2]){
            number = x * 2; 
        }
        if(a[x] > a[number]){
            swap(a[x] , a[number]);
            x = number;
        }
        else{
            break;
        }
    }
}

void push(int x){
    a[len] = x;
    len ++;
    shiftup(len - 1);
}

int Return(){
    return a[1];
}

void Delete(){
    a[1] = a[len - 1];
    a[len - 1] = 0;
    len --;
    shiftdown(1);
}
int main(){
    int x,s;
    int c = 1;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> x;
        if(x == 1){
            cin >> s;
            push(s);
        }
        else if(x == 2){
            ans[c] = Return();
            c ++;
        }
        else if(x == 3){
            Delete();
        }
    }
    for(int i = 1; i <= c - 1; i++){
        cout << ans[i] <<endl;
    }
    return 0;
}

附件2 堆的STL实现

代码描述

这段代码是堆的STL实现的基本格式,注释会对代码进行解释,堆为小根堆。

源代码

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

bool cmp(int a, int b){//比较函数 
    return a > b;
}  

int n , a[10001];

int main(){
    cin >> n; //  输入6 
    for(int i = 1; i <= n; i++){
        cin >> a[i]; //输入2 3 5 8 1 9 
    }

    make_heap(&a[1] , &a[n] , cmp);
    //此时,堆内元素为1 2 5 8 3 9 

    cin >> a[n]; //输入4 

    push_heap(&a[1] , &a[n + 1] , cmp); 
    //此时,堆内元素为1 2 4 8 3 5 9

    pop_heap(&a[1] , &a[n + 1] , cmp); 
    //此时,堆内元素为2 3 4 8 9 5

    sort_heap(&a[1] , &a[n + 1] , cmp);
    //结果肯定是有序的…… 

    for(int i = 1; i <= n; i++){
        cout << a[i] << " ";  
    }

    return 0;
} 

附件3 优先队列的STl实现

这份代码是优先队列的STL实现,同时也是洛谷P1090的标程,

因此,本代码开启防作弊功能。

但不要担心,优先队列的模板部分是没有错误的。

#include<iostream>
#include<queue>

using namespace std;

void work(){
    return ;
}

priority_queue<int , vector<int> , greater<int> > Q;

int ans = 0;

int main(){
    work();
    int n , a;
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a;
        Q.push(a);
    }
    while(Q.size() >= 2){
        int x = Q.top();
        Q.pop();
        int y = Q.top();
        Q.pop();
        ans += x + y;
        Q.push(x + y);
    }
    cout << ans <<endl;

    return 0;
} 

更新日志

  • 2019.2.10 更新了标签,修改了少量错别字

  • 2019.2.23 更新了STL部分

  • 2019.3.30 更新了priority_queue部分

……


THE END