堆？怼？

前言

大前天（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[]的数组表示堆，那么

  • $Heap[x] \leq Heap[2x] \& Heap[2x + 1] $(小根堆)。

  • $Heap[x] \geq Heap[2x] \& Heap[2x + 1] $(大根堆)。

同时，我们还可以看出，堆顶元素一定是最大（或最小）元素。

堆的操作。

现在你可能要问：“这么麻烦的堆，有什么用吗？”

当然是拿来怼人啦

咳咳，一个堆支持以下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后面一定要有一个空格，否则的话会被编译器识别为右移运算符“>>”

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

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