堆

Created2021-02-22Updated2021-02-22

堆

堆

一、堆的定义

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

  1. 堆中某个节点的值总是不大于或不小于其父节点的值；

  2. 堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
堆是非线性数据结构，相当于一维数组，有两个直接后继。
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(k_i <= k_2i , k_i <= k_(2i+1))或者( k_i >= k_2i, k_i >= k_(2i+1)), (i = 1,2,3,4…n/2)

二、手写一个堆

手写堆的存储方式：用一维数组存储树的每一个节点。

基本操作

（这里以小根堆为例）

对于不满足堆的性质的一个节点做调整：

down（向下调整）：将它与它的左二子，右儿子比较大小，并与最小值交换位置（否则不满足堆的性质），递归的完成这个过程。（时间复杂度O($logN$)）

1
2
3
4
5
6
7
8
9
10
11
void down(int k)
{
	int mink=k;
	if(2*k<=cnt and h[2*k]<h[mink])mink=2*k;
	if(2*k+1<=cnt and h[2*k+1]<h[mink])mink=2*k+1;
	if(mink!=k)
	{
		swap(h[mink],h[k]);
		down(mink);
	}
}

up（向上调整）：将它与它的父节点比较，如果比父节点要小，那么就与父节点交换，递归的完成这个过程。（时间复杂度O($logN$)）

支持的功能：

  1. 插入一个数

    1
    heap[++cnt]=x; up(cnt);

  2. 求集合中的最大/小值

    1
    ans=heap[1];

  3. 删除集合中的最大/小值

    1
    2
    heap[1]=heap[cnt]; cnt--;
    down(1);

  4. 删除任意一个元素

    1
    2
    heap[k]=heap[cnt];cnt--;
    down(k);up(k);//虽然都写了但是这两个操作只会执行一个，看大小来决定

  5. 修改任意一个元素

    1
    2
    heap[k]=x;
    down(k),up(k);

  6. 由数组建堆（建堆复杂度看似O($NlogN$)，实际可求出为O(N)）

    1
    2
    for(int i=1;i<=n;i++)cin>>h[i];
    for(int i=n/2;i>=1;i--)down(i);//为什么是n/2：因为最后一层不用管，只需要保证整个堆满足堆的性质即可

三、模板和例题

洛谷P1177 快速排序：用堆排序来做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100050;
int n,m;
int cnt=0;
int h[N];
void down(int k)
{
    int mink=k;
    if(2*k<=cnt and h[2*k]<h[mink])mink=2*k;
    if(2*k+1<=cnt and h[2*k+1]<h[mink])mink=2*k+1;
    if(mink!=k)
    {
        swap(h[k],h[mink]);
        down(mink);//递归完成这个过程，直到出现一个满足堆性质的子树（不用继续调整）
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
    }
    cnt=n;
    for(int i=n/2;i>=1;i--)
    {
        down(i);//建堆
        //为什么是n/2：因为最后一层不用down，只需要保证整个堆满足堆的性质即可
    }
    while(n--)
    {
        cout<<h[1]<<" ";
        h[1]=h[cnt];
        cnt--;
        down(1);
    }
    return 0; 
}

洛谷P3378 【模板】堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1000050;
int n,m;
int cnt=0;
int h[N],ph[N];
void down(int k)
{
    int mink=k;
    if(2*k<=cnt and h[2*k]<h[mink])mink=2*k;
    if(2*k+1<=cnt and h[2*k+1]<h[mink])mink=2*k+1;
    if(mink!=k)
    {
        swap(h[k],h[mink]);
        down(mink);//递归完成这个过程，直到出现一个满足堆性质的子树（不用继续调整）
    }
}
void up(int k)
{
    while((k/2) and h[k/2]>h[k])
    {
        swap(h[k/2],h[k]);
        k/=2;
    }
}
void ins(int x)
{
    h[++cnt]=x;
    up(cnt);
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    int op;
    int x;
    while(n--)
    {
        cin>>op;
        if(op==1)
        {
            cin>>x;
            ins(x);//插入x这个数
        }
        else if(op==2)
        {
            cout<<h[1]<<endl;//输出最小的元素
        }
        else
        {
            h[1]=h[cnt];
            cnt--;
            down(1);
        }//删除最小的元素
    }   
    return 0; 
}