堆的定义

随便翻开一本数据结构入门书,都能看到堆的定义.堆是一个完全(除最底层外都是满的)二叉树,并满足如下条件:

    1. 根结点若有子树,则子树一定也是堆.
    2. 根结点一定大于(或小于)子结点.

因为要求堆必须是完全二叉树,所以可以用线性的数据结构,比如数组,来实现堆.利用数组data[..]实现,则对于长为N的堆中的元素从1到N排列,有:

    • i的父结点:Parent(i)=i/2
    • i的左叶子:Left(i)=2*i
    • i的右叶子:Right(i)=2*i+1

不失一般性,下文中提到的堆特指最大堆.下图就是一个最大堆.

240px-Max-heap

堆的操作

堆通常主要有以下两种操作:

    • insert: 因为需要维持堆的完全二叉树形态,需要先将节点x插到新的位置,然后把x做上升调整(元素交换)到合适的位置,即当x比它的父亲小时,把x与它的父亲交换.
    • delete: 因为需要维持堆的完全二叉树形态,需要先用”最后一个节点”x把要删除的节点(根节点)覆盖掉,再把x下降到合适的位置,即当x比它的默一个儿子大时,把x和它的较小儿子交换.

堆的两种操作用伪代码表示如下:

insert(e)     //自底向上

将e放在堆尾
while e不在根节点并且e>parent(e)

交换e及其父节点

delete(data[])    //自顶向下

用一变量tmp保存堆中元素个数size
交换堆首与堆尾      //为方便叙述,以x表示原堆尾元素
堆元素个数减1
while 以x为根的子树不满足堆的性质

交换x及其一符合条件的孩子节点

堆的应用

[题目1] Dull Game (via: sicily 1778)

There are infinite balls with distinct number and distinct weight in a pool. At the beginning there is an empty box, too. Ivan and Kevin are going to play the game for N rounds. In the ith round, Ivan will take away Ai balls from the pool and put them into the box. Then Kevin will choose the first Bi heaviest balls from the box and throw them away. Too stupid, isn’t it!
What Ivan and Kevin want to know is which is the heaviest one among the remaining balls in the box after N rounds done.

[分析] 这是一道赤裸裸的堆排序,给出代码:

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/* source code of submission 262362, Zhongshan University Online Judge System */
#include<iostream>
#include<queue>
using namespace std;
#define MAX 100000
int test,n,a,b;
typedef struct node{
    int num;
    int weight;
}Node;
long st_num;
Node st[MAX];
bool operator <(Node a,Node b)
{
    return a.weight<b.weight;
}
void swap(int x,int y)
{
    Node temp=st[x];
    st[x]=st[y];
    st[y]=temp;
}
void st_insert(Node m)
{
    st[st_num+1]=m;
    st_num++;
    int num=st_num;
    while(num!=1)   
    {
        if(st[num].weight>st[num/2].weight)
        swap(num,num/2);
        num/=2;
    }
}
void st_delete()
{
    int num=st_num;
    swap(1,num);
    st_num--;
    num=1;
    while(num<=st_num/2)
    {
        if(st[num*2].weight>st[num*2+1].weight)
            if(st[num*2].weight>st[num].weight)
                swap(num*2,num);
        else if(st[num*2].weight<=st[num*2+1].weight)
            if(st[num*2+1].weight>st[num].weight)
                swap(num*2+1,num);
        num*=2;
    }
}
Node st_top()
{
    Node top;
    top=st[1];
    return top;
}
int main()
{
    cin>>test;
    int i;
    while(test--)
    {
        st_num=0;
        cin>>n;
        priority_queue<Node>pq;
        while(n--)
        {
            cin>>a>>b;
            for(i=0;i<a;i++)
            {
                Node temp;
                cin>>temp.num>>temp.weight;
                pq.push(temp);
            //  st_insert(temp);
            }
            for(i=0;i<b;i++)        
            //  st_delete();
                pq.pop();
        }
        cout<<pq.top().num<<" "<<pq.top().weight<<endl;
    //  cout<<st_top().num<<" "<<st_top().weight<<endl;
    }
    return 0;
}

[题目2] 可怜的奶牛(via: 黑书 P90)

农夫John有n(n<=100,000)头奶牛,可是产的奶太少,John决定每天把产奶最少的一头奶牛做成牛肉干吃掉.由于总有一点舍不得,John打算如果同时有两头或两头以上奶牛产奶最少,当天就一头也不吃.需要说明的是,奶牛产奶是周期性的,每头奶牛产奶的周期Ti可能不同,但不会超过10.John数学很差,你能帮他计算M天后,有多少头奶牛能够幸免于难吗?

[分析] 此题最容易想出的方法就是简单的模拟,每天根据奶牛的产奶量找出最小值,则复杂度为O(n),总复杂度为O(T*n).其中,T为模拟的天数,因为周期不超 过10,如果有的牛永远也不会被吃掉,那么最多需要模拟2520天(2520是1,2,..10的最小公倍数) 才能确定答案,复杂度难以忍受.

根 据黑书的分析,我们可以换一种思路,将周期相同的奶牛归位同一类,则最多有10类奶牛,同一类奶牛在被吃光之前,每天的最小产奶值也是周期性的,记周期为 t.因此在模拟时,每天只要比较10类奶牛中每类牛的最小产量就可以了,则每天的复杂度为O(k),k为最长周期,需要模拟T天,复杂度为O(T*k). 对k类牛维护k个表,每个表为一对应类所有牛产量构成的最小堆,一类牛中数量最多为n,故复杂度为O(k*nlogn).综上分析知,总的复杂度为 O(T*k+k*nlogn),远远小于O(T*n).

特殊的堆:杨式图表

杨式图表(Young Tableau) 是一个矩阵,它满足条件:

    • 如果格子(i,j)没有元素,则它右边和上边的相邻格子也没有元素.
    • 如果格子(i,j)有元素a[i,j],则它右边和上边的相邻格子要么没有元素,要么比a[i,j]大.

下面,不加证明地给出一个定理:

1~n所组成的Young Tableau的个数可以由下式给出:

    1. a(1)=1,a(2)=2
    2. a(n)=a(n-1)+(n-1)a(n-2)

例如,由1,2,3这三哥元素组成的杨式图表一共有4个:

YoungTableaux_1000

如果将没有元素的格子看成正无穷,则上述的两个条件可以看成一个:杨式图表的每行从左到右递增,每列从上到下递增.如果沿着矩阵的左对角线看,则杨式图表是一个二叉堆.

下面给出黑书中对于杨式图表的插入算法和查找算法的描述:

    • 插入算法(bumping算法): 从最底行开始,从左到右找底一个比x大的数.如果找不到,将x插到行尾;如果找到了符合条件的y,交换x和y,并从第二行(注意,最底层行号为1,倒数第二层行号为2,以次类推)开始用累死的方法插入y.由于行数(这里,黑书写错了)递减,所以算法必定终止.
    • 查找算法: 从n*m的矩阵底行最右列开始查找.如果当前元素比x大,向左查找(因为当前列一定不存在该元素),一旦遇到比x大的元素就向上查找(因为当前行的左边不可能有该元素),直到找值等于到x的元素为止.容易知道,总的比较次数不超过m+n.

最后,给出一道活生生的杨式图表的题目:

[题目3] Young Tableau问题的描述是这样的,一个由N个小方块组成的阵列(不一定要是矩形,可以是一个任意”光滑”且”单调”的组合),从1到N这N个数填入方块中,要求全部填满并且一个数只能填一个方格一次.并且满足,每个数的上方的数和左方的数比它大.求最后一共有多少种填法.比如一个4*4格子的正方形,1~16这16个数按照上述规则填入,那么一共多少种填法.

update: 未完,我体力不支了,不一定续写,thanks to the sucking net speed.