分类: 2009 November

堆排序

堆的定义

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

    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.

使用字典树–Using Tries

原文:Using Tries 作者:luison9999

翻译 Arthur1989@sysu

Introduction

在文本中索引和搜索一段字符有很多种算法和数据结构,某些被包含在标准库中,但有些并没有.数据结构trie就是这么一个未被包含在标准库中的很好的例子.

以word表示一个字符串,dictionary表示word的集合.在已经有了一个dictionary的情况下,当我们想知道一个特定的word是否在dictionary中时,trie数据结构可以帮上大忙.但是,也许你会问,”既然set和哈希表已经能够实现这一查询了,为什么还需要trie呢?”下面是两个主要的理由:

  • trie插入和查询字符串的时间复杂度是O(L)(L表示一个特定字符串的长度).这比起set可要快上不少,即便和哈希表比较,trie还是稍微更快的.
  • set和哈希表只支持在dictionary中查找到希望查询的字符串完全匹配的字符串;而trie允许我们容错查找,比如说,字符不一致,共同前缀,字符丢失等等.

trie不仅在TopCoder类型的比赛中很实用,它在软件项目中也有相当多的实际应用.举个例子,考虑一下网络浏览器.你知道浏览器是如何根据已输入的文字自动填充或者给出给出候选输入的吗?是的,通过trie你可以轻易地实现这个功能.你知道拼写检查器是怎么知道你所输入的每一个单词是否在词典中的吗?答案还是一样的,通过trie.你同样可以通过trie,判断输入的单词是否在词典中存在,如果不存在的话给出一个改正的建议单词.

What’s a Tree?

可能你早就知道trie的强大了,但是也许你并不清楚trie究竟是什么,它为什么被命名为trie呢?其实,trie的名字是”retrieval”的中缀,因为trie可以通过前缀在词典中搜索可能的字符串.trie数据结构主要基于以下的几点想法:

  • trie是一棵树,每一结点是一个字母或者是一个前缀.
  • 树根表示一个空的字符串(“”),根的直接后继结点表示长度为1的前缀,深度为2的结点表示长度为2的前缀,深度为3的结点表示长度为3的前缀,以此类推.换句话说,深度为k的结点表示长度为k的后缀.
  • 以v和w表示trie树的两个结点,v为w的直接前驱,那么v的前缀必须是w的前缀.

下图表示了一棵包含单词”tree”,”trie”,”algo”,”assoc”,”all”,和”also”的trie树.

alg_tries

注意,trie树的每一结点并不保存单词完整的前缀或者是单词本身,它仅仅保存一个字母,程序会记下它所有祖先存储的信息.

Coding a Trie

trie树可以通过不同的方法构造,有些方法可以用来在字典中查找与目的字符串略微有些不同的所有其他字符串,但是有些方法仅仅支持完全匹配的查询.本文介绍的是后者.trie的实现将以伪代码的形式给出,因为不同的人使用不同的语言.

我们将实现下面4个功能:

  • 插入.该功能允许向词典中插入单词.
  • 统计前缀.该功能统计所有以一特定字符串作前缀的单词的数目.
  • 统计单词.该功能统计词典中与一给定的字符串完全匹配的单词数目.
  • 这里的trie树仅仅支持英文字母表中的字符.

我们打算构造一个struct,用它的数据域来记录结点保存的信息.为了知道与一给定的字符串匹配的单词的数目,每一结点需要有一个变量来表示该结点代表一个完整的单词还是仅仅一个前缀(为简洁起见,给定的单词被认为是一个前缀),它还需要一个变量来统计以给定的单词作为前缀的单词的个数(词典中同一单词可以重复出现),这用一个整形变量就足够了.

正如前面所分析的,每个结点需要一个整形变量prefixes,它表示词典中以该结点代表的前缀为前缀的单词个数.同样,每个结点需要关联到它的所有可能儿子结点(26个关联).理清所有这些细节之后,我们可以知道,struct体需要包含下面的成员:

structure Trie

integer words;
integer prefixes;
reference edges[26];

而且,我们需要实现以下的函数:

initialize(vertex)
addWord(vertex, word);
integer countPrefixes(vertex, prefix);
integer countWords(vertex, word);

首先,以下的代码实现结点信息的初始化:

initialize(vertex)

vertex.words=0
vertex.prefixes=0
for i=0 to 26

edges[i]=NoEdge

addWord函数有两个参数,单词插入所在的结点,插入的单词.当一个字符串string被添加到结点vertex时,我们将根据word的首字母,将它加入相应的vertex的分支,然后将word的首字母去掉.当找不到相应的vertex分支时,我们需要对vertex结点新建一个分支.(Arthur989注:一直递归着这么做下去,直至word为空)所有TopCoder比赛支持的语言都能够在常数时间内删去一个字符串的首元素,而无需拷贝原字符串或者移动字符串的其他元素.

addWord(vertex, word)

if isEmpty(word)
vertex.words=vertex.words+1
else

vertex.prefixes=vertex.prefixes+1
k=firstCharacter(word)
if(notExists(edges[k]))

edges[k]=createEdge()
initialize(edges[k])

cutLeftmostCharacter(word)
addWord(edges[k], word)

函数countWords和countPrefixes是非常相似的.如果(在递归过程中)程序查询的字符串变为空,那么程序只要返回(此时递归所在的)结点所存储的统计变量prefixes就可以了.如果程序查询的字符串非空,我们需要递归查询字符串首字母对应的分支,当分支不存在时,程序将返回0.

countWords(vertex, word)

k=firstCharacter(word)
if isEmpty(word)

return vertex.words

else if notExists(edges[k])

return 0

else

cutLeftmostCharacter(word)
return countWords(edges[k], word);

countPrefixes(vertex, prefix)

k=firstCharacter(prefix)
if isEmpty(word)

return vertex.prefixes

else if notExists(edges[k])

return 0

else

cutLeftmostCharacter(prefix)
return countWords(edges[k], prefix)

Complexity Analysis

通过上文的介绍,你已经感性地知道在trie树中查询和插入一个字符串的复杂度是线性的,但我们却还没着手于具体的分析.在查询和插入的过程中,根据字符串找到下一层对应的儿子是可以在常数时间内实现的,每次程序递归到下一分支时,字符串首字母将被删除;如果字符串长度为L,查询和插入将做L次的递归,因此,这两个操作的时间复杂度为O(L).tire树耗费的内存取决于存储分支的具体方法,以及trie树中有多少单词共享相同的前缀.

Other Kinds of Tries

在我们的介绍中,trie树结点局限于存储小写的英文字母,事实上,它还可以存储其他的信息.我们可以用结点来存储比特或者是字节,此时trie树可以表示任意的数据类型,而不再只是字符串了.发挥你的想像来使用trie树吧!比如说,假设你想在字典中查找一个单词,但是该单词缺失了一个特定的字母,你可以这么修改代码:

countWords(vertex, word, missingLetters)

k=firstCharacter(word)
if isEmpty(word)

return vertex.word

else if notExists(edges[k]) and missingLetters=0

return 0

else if notExists(edges[k])

cutLeftmostCharacter(word)
return countWords(vertex, word, missingLetters-1)
这里我们删去字符串首字母,但不递归查找下一分支.

else

这里我们考虑了两种可能:字符串首字母已被删除和未被删除
r=countWords(vertex, word, missingLetters-1)
cutLeftmostCharacter(word)
r=r+countWords(edges[k], word, missingLetters)
return r

比起原来的程序,修改后的代码的时间复杂度会更高,但是它比检查某一单词的所有子集来得更快.

Problems to Practice

WordFind SRM 232
SearchBox SRM 361
CyclicWords SRM 358
TagalogDictionary SRM 342
JoinedString SRM 302
CmpdWords SRM 268
Scruffle 2007 TCCC Marathon Online Round 1

无聊(1)

荒废了一个多星期..突然想要写点什么.

首先仍旧是感情.先谈谈老丘的.老丘最近在泡妞,这没什么不好的.地球上那么多善男信女,多一对也不打紧.可是,杀千刀的是,老丘一直在向我输出泡妞的好处,这是很不厚道的.老丘说,为了能在女生面前有个更好的形象,所以会自觉不自觉地注意到自己的缺陷.比如说,太过偏僻,又比如说,太过冲动.这话一点不假,放我身上恐怕也这么想.可是当老丘谈到要多读读汪国真同学的诗歌,看看discovery频道的人文时,我想,真t的,泡个妞还得这么麻烦,莫名其妙地成了个恶心的文学男…老丘看来,这可真是好事一桩,不但能读书还能送个女生,一点不亏的买卖.既然老丘都这么想了,我也不好说什么,奉上一句话,理论上,实际是接近于理论的;实际上,理论是接近于实际的.

然后是我遇到的感情事了.前几天,师傅很神奇地给我发了封邮件.我和师傅初一就认识了,数数到现在也有8年了.可惜从初三到上个月之前,6年的时间里从没再见面过.我和师傅关系一直很好,记忆中除了初二吵过一架之外.初中和高中的日子里,我们一直都是在写信.很无奈的是,上高中时,我把初中的信扔了.高考前几天,我又在东中后山亲手种的树下烧了好几封,剩下的也全无踪迹了.我不无天真的想,如果从没丢过信的话,摞起来该是厚厚的一叠了吧.信丢了自然是有愧歉的,而这一愧歉就是几年..收到师傅的邮件,我才知道,师傅去年搬家时也把信扔了.看来是两不相欠了.师傅初三送的一套邮票如今也早不见了,唯一还在的就是去年生日时师傅送的一件上衣和三张我非常非常喜欢的班得瑞CD了.师傅是我少有的几个聊得来的异形朋友了.多亏常和师傅写信,不然我的本来就单调苍白的初中高中生活怕是更会减色不少.上次见面时,发现师傅成熟了好多,最不错的一点是坚持着自己喜欢的.世界观很不错,价值观也很健康,不再像以前那个有那么一点霸道的大姐大了.

再然后,最近在烦着该不该读研呢.师傅是”举双脚赞成的”,老丘说应该慎重考虑.爷爷是要我读研的,因此,我应该是不读研了.我没打算用一个3年去再一次证明爷爷错了,中大的4年已经很浪费青春了.其实,读不读研有那么要紧吗,也许是我从没决定好,所以才这么纠结.也许,follow my heart就行了.

最后,什么时候我才能不懒呢.

_________________

代码:
sudo apt-get install girlfriend
正在读取软件包列表… 完成
正在分析软件包的依赖关系树… 完成
有一些软件包无法被安装。
下列的信息可能会对解决问题有所帮助:
下列的软件包有不能满足的依赖关系:
girlfriend: 依赖: house但是它将不会被安装
girlfriend: 依赖: car但是它将不会被安装
house,car: 依赖: money但是它将不会被安装
E: 无法安装的软件包