堆，就是一陀一陀的东西。头重脚轻不算堆，要上面小下面大才算一个堆。堆是一棵二叉树，满足下面的始终比上面的大。它和二叉查找树比较起来既有好的又有不好的：好的就是要想知道数据里的最小值时根本就不用找了，直接就是最顶上的那个了；不好的就是堆除了这个以外基本上不能做别的事了。除了最顶上的那个以外，你几乎没办法控制其余的部分。当然，插入和删除数据这种基本操作还是可以做的。插入就是把数据暂时先放在最下面的某个位置，然后通过与它上面一个进行比较、交换不断往上冒直到已经到了自己的位置不能再向上为止。删除反起来，通过不断交换往下沉一直沉到底。因为是往下走，所以要考虑到一个把左边的放上来还是把右边的放上来的问题。当然，为了保证堆上小下大的性质，应该把小的一边换上来。刚才说过，由于你只能“看”到最顶上的东西，不知道中间部分是什么样，我们通常只删除最小的（最上面的）那个节点。其实堆还有一个最大的好处：容易写代码。因为我们可以有意让数据把树“排得满满的”，满到它是一行一行挨着排下来的。这叫做“完全二叉树”。我们可以给完全二叉树编个号，从上到下从左到右挨着数下来。根是1，找左儿子就乘2，找右儿子就乘2加1，找它爸就 div 2。以后叫谁就是谁，很方便。这样整个树就可以用一个数组实现了。由于堆基本上只用来找最小，因此如果某个问题要求很复杂的话，最好还是用成二叉查找树；当然，如果问题只要求插入、删除和找最小三种操作，你应该毫不犹豫地选择堆，毕竟找最小时堆方便得多，写起又简单。什么时候出现这种问题呢？比如说，我的女友排起队的，我每次要选一个最纯洁的，就是受那些的影响最小的人。每当我遇见了一个新的美女，我就把她放在这个队伍里合适的位置供我以后娱乐。这时，我只关心每次插入、取最小和删最小。这个队伍就可以用一个堆来优化。因此，堆还有一个形象的名字叫优先队列。如果谁问题目要求不找最小找最大怎么办，那人肯定是个傻子，把堆变通一下，上大下小不就完了吗？

    研究堆麻烦的地方就是堆的合并。如何把两个堆合并成一个堆？这个解决了很有用，至少上面的这些操作跟着全部统一了：插入就是与一个单节点的堆合并，删除根就是把根不要了，把根的左右两边（显然还是堆）合并起来。一个简单的办法就是递归地不断把根大的堆往根小的堆的右边合并，把新得到的堆替换原来的右儿子。注意递归过程中哪个根大哪个根小是不停在改变的。这样下来的结果就是典型的“右倾错误”，而且破坏了完全二叉树的完美。为此，我们想要随时保证堆的最右边尽量少。于是，干脆不要完全二叉树了，不过是多写几行代码嘛。这个不存在像二叉查找树那样“某一边越做越多”的退化问题，因为对于一个堆来说，反正我只管最顶上的东西，下面平不平衡无所谓，只要不挡我合并的道就行。于是，我们想到人为下一个能让堆尽量往左边斜的规定。这个规定就是，对于左右两个儿子来说，左边那个离它下面最近的两个儿子不全（有可能一个都没有）的节点的距离比右边那个的远。这规定看着麻烦，其实还真有效，最右边的路径的长比想像中的变得短得多。这就叫左式堆（左偏树）。这下合并倒是方便了，但合并着合并着要不了多少次右边又多了。解决的办法就是想办法随时保持左式堆的性质。办法很简单，你合并不是递归的吗？每次递归一层后再看看左右两边儿子离它下面没有两个儿子的节点哪个远，如果右边变远了就把左边右边调一下。由于我们已经没有用数组实现这玩意了，因此链表搞起很简单。这个对调左右的方法给了我们一个启发：哪里还要管什么到没有两个儿子的节点的距离嘛，既然我每次都在往右合并，我为什么不每次合并之后都把它对调到左边去呢？这种想法是可行的，事实上它还有一个另外的名字，叫斜堆。

    二项堆更强，它也是堆，也能合并，不过它已经超越了堆的境界了：它不是一个堆，而是满屋子的堆。也就是说，找最小值不能再一下子找到了，而是要把二项堆中的每个堆的顶部都看一下。二项堆的合并也很强，直接把根大的堆放在根小的堆的下面。这意味着二项堆的每个堆都可能不是二叉树了。这增加了编程的难度，不过可以用一个叫做“左儿子右兄弟”的技巧来解决问题。这个技巧，说穿了就是仍然用二叉树来表示多叉树：把树画好，然后规定节点的左儿子是下一层的最左边那个，右儿子就是它右边那个。就是说，左儿子才是真正的儿子，右儿子不过是一起生出来的。为了让二项堆好看些，让堆的个数和大小保持在一个能快速操作的数目和比例内，二项堆作出了一个明智的规定：每个堆的大小（总的节点个数）只能是1、2、4、8、16…中的一个，且每种大小的堆只能有一个。若干个互不相同的2的幂足以表示任意一个正整数，因此这个规定可以保证不管多大的二项堆都能表示出来。保持这个性质很简单，遇到两个大小相等的堆就合并起来成为一个大一号的堆。由于总是两个大小相等的堆在合并，因此二项堆中的每一个堆都有一个奇妙的样子，看看本文结束后下面附的一个大小为16的堆的示意图，再看一下，再看一下，你就能体会到了。图下面有一个用“左儿子右兄弟”法表示的同样的树，其中，往下走的线是左儿子，往右走的线是右儿子。

    最后简单说一下Fibonacci堆。保持一个跟着变的数组记录现在某个节点在堆中的位置，我们还是可以对堆里的数据进行一些操作的，至少像删除、改变数值等操作是完全可以的。但这个也需要耗费一些时间。Fibonacci堆相当开放，比二项堆更开放，它可以不花任何时间减少（只能是减少）某个节点的值。它是这样想的：你二项堆都可以养一屋子的堆，我为什么不行呢？于是，它懒得把减小了的节点一点一点地浮上去，而是直接就把它作为根拿出来当成一个新的堆。每次我要查最小值时我就再像二项堆一样（但不要求堆的大小了）一个个合并起来还原成一个堆。当然，这样的做法是有适用范围的，就是前面说的数值只能是减少。在什么时候需要一个数值只减少不增加的堆结构呢？莫过于Dijkstra一类的图论算法了。所以说，这些图论算法用Fibonacci堆优化可以进一步提速。



Matrix67原创
做人要厚道 转帖请注明出处

    4月7日买起来看，前几天才看完。这可以说明很多问题，比如，学习很紧张，没有时间；书本身很好，很有看头；看书看得很细心，很有耐心。
    打算大致写一下书里的内容。
    Data Structures and Algorithm Analysis in C, Second Edition，机械工业出版社。封面很丑，一个黑底版，上面有些大理石花纹，正中间生硬的摆一个原版封面，同样丑。一共12章，近400页。
    400多页是很多的。我们必须要“把厚书读薄”，厚的变薄的，薄的变一页，一页变一行，一行变成一个字。因此，我要在有限的字数内把整本书说完。

    算法分析，就是复杂度的问题。复杂度只算“最要命的”，比如，执行n^2的算法前来个快排根本不拖速度，n^2多的都豁出去了不在乎区区一个nlogn。书里对复杂度进行了严格的定义，包括O()、o()、Θ()、Ω()四种符号。简单地说，O(n^2)就是顶破天了搞个n^2次；o(n^2)就是天花板不到n^2，比n^2矮一点（比如希尔排序就是o(n^2)，因为它再倒霉也达不到n^2）；Ω(n^2)就是说某个算法随便怎么至少都要耗费n^2，比如所有基于比较的排序都是Ω(nlogn)；Θ(n^2)就是说它即是O(n^2)又是Ω(n^2)，被天花板和水泥地夹在中间了，动不了了，就是它了。这里面有一个经典的例子，就是最大子序列（找数列中连续一段数之和最大）的四种算法，复杂度分别为O(n^3)、O(n^2)、O(nlogn)和O (n)。这书一个特色在于，对每种数据结构都有严格的算法复杂度证明，这往往是看上去最头痛的部分。

    表、栈和队列是三个基本的数据结构。说穿了表就是把数据找起来排排坐吃果果，找什么东西都来把整个队伍找一遍。栈就是一个桶，后放进去的先拿出来，它下面本来有的东西要等它出来之后才能出来，就好像你看到了一个丑人不可能今天的中饭还没吐出来就先把早饭吐出来了。栈是拿来模拟多个过程的调用的（比如递归），实际点的用途就是表达式计算。队列好比堵车，先进去的先出来。先进队先买票，不能插队。常拿来实现广搜。

    树，是一种植物，有很多枝枝丫丫。不同的是这里的树是倒着的，树枝朝下长。最上面叫根，尖尖的地方叫树叶，生出树叶的是他爸，他爸生的是他儿子。不管是根是树叶还是儿子还是儿子他爸都叫节点。我们常常把数据储存在节点上，并且以后还要不断地插入、改变和删除数据。
    二叉树就是每个分叉的地方最多分两个岔，而且还分得清左右。二叉查找树就是说把数据存在节点上，而且左边的都比他爸小，右边的都比他爸大，以后要找哪个数就可以只找其中的一边，一半一半地扔掉。在二叉查找树里也可以插入一个数，删掉一个数（只有一个儿子好办，有两个就把右边的最小的一个拿来替代这个），找最小的数（一直往左走），找最大的数（一直往右走），但是容易搞着搞着的树就变畸形了，比如说左边猛起长右边萎缩导致以后往左边走要走很久。我们就需要一种方法来让树左右差不多一样多而且左边的值仍然比右边的小。事实上这种方法已经找到了，而且不只一种方法，而是一卡车的方法，比如AVL、Splay、红黑树、Treap等。几种方法都靠一个叫“旋转”的技巧，就是把几个节点怎么个一转，左边的就跑到右边去了一点。看下面这个图你就明白了。

         ①                   ②
        /  \      旋转       /  \
      ②   ZZ    ------>    XX  ①
     /  \                      /  \
    XX  YY                    YY  ZZ

这样一来左边就少了，如果左边的XX本来很多的话就可以往上提一层从而平衡。同样地，右边多了反过来做就是了。这只是最简单的“单旋转”，事实上还有很多其它的较复杂的旋转方法。Splay树就是把刚才访问过的节点转啊转啊转啊转转到最顶上去，Treap就是每个节点附加一个随机的数，随时通过旋转保持儿子的这些随机数比他爸大，其余的有点复杂。这些方法都能使二叉查找树相对地平衡一些，防止畸变导致的时间浪费。
    B-树和二叉查找树有两个不同，一个是节点不存数据，数据全在树叶子上，二个是它不一定是二叉。数据仍然左边小右边大方便查找。每个节点最多的儿子数有限制，最多三叉的叫2-3树，最多四叉的叫2-3-4树。因为只有树叶上有数据，所以可以递归地用分裂的方法处理新插入后出现的分叉比规定的最多的儿子个数时还多的情况。比如，2-3树中如果哪里分了四个岔，就把它重新分成两个两个的岔。我们还规定，除了根以外，每个节点最少的儿子数是规定的最多儿子数的一半，除不尽取上整。容易想到，删除的话可以把插入时的分裂反过来做，什么时候只剩一个儿子了就和旁边的合并起来。

    Hash表又叫散列表，一般用于判断有没有重复。比如我想找我们班有没有两个一天生的，我们不必每两个人都来比较一次，而是准备一个年历，让人一个一个上去在他的生日那天那里画一个圈，如果谁要画圈时发现那里已经有一个圈了，就找到了一对。这个很简单，不说了。
    那天班上流行一个心里测试，当时我还真发现了一个和我一天生的，女的。

Matrix67原创
做人要厚道 转帖请注明出处

    刚看完。看到过的最好看的一集House了。
    先告诉不知道House的，这是一个我喜欢的美剧，讲一个名字叫House的医生和他的团队专门负责送来的疑难杂症，那种最奇怪的病历。House这人很幽默；情节结尾往往很有戏剧性。
    通常这种系列剧的最后一集总会发生一件大事。这一集开头时，House团队正在讨论一个很怪的病例，突然冲进来一个人给了House两枪。片头曲过后， House从病床上醒过来，显然已经脱离生命危险了。他继续和他的队伍研究那个病例。House队伍里的那些人很聪明，House打了一些形象的比喻，那些人立刻就明白了他的意思，进行相应的检查。House自己也知道，头几次设想就猜对的可能性极小。在他的人向他汇报结果之前House就猜到每次测试结果都显阴性。不久，所有设想都被否定。这个病人的病前所未有的不可思议，没有任何理论支持他的症状。House觉得他们肯定漏掉了什么，他一定是默认了某个很基础的东西。他叫他的人想想一些最基本、最底层的东西，比如，检查一下这个病人究竟是不是个“人”。
    与此同时，House自己的精神状况出了一些问题。他估计，他在中枪后的手术中一定有什么东西被碰到了，导致他现在常常出现幻觉。他甚至有时候忘记了自己“是怎么来到这里的”。
    最后，House完全明白了。他明白了为什么他的团队没有把有精神毛病的他踢出队伍，为什么他的每次比喻都能被正确的理解，为什么他每次提出设想都没有遭到反驳，为什么在他的人还没来汇报时他事先就知道结果，以及为什么他精神恍惚记不起东西。因为他忽略了一个最最基本的东西：这些东西不一定是真的。他默认了一切都是真实的。片头曲过后的一切都是在他意识中的东西，都是他的幻觉，都是他自己想出来的。一个人在梦中当然知道别人想说什么，因为别人要说的话也是他自己想出来的。同时，梦也常常不是完整的、清晰的，而是模糊的、断断续续的。
    他必须做出一些不能被他自己的大脑接受的事情来摆脱幻觉。于是，他跑到病人那里去，当着他的队伍用机械手术刀把病人的腹部剖成两半。
    最后一个镜头——House在一个担架上睁开眼睛，一群人跟着他跑。时间不过是中枪后的几分钟，他还在推往手术室，旁边的人告诉他You'll be OK。之前的他全活在昏迷后的幻想中。

做人要厚道 转帖请注明出处

    今天没事干，去看电影去了。真是好久都没去电影院了，记得最近的一次也是初三的时候和（传说中的）ZJ看《THE MATRIX REVOLUTIONS》和《THE CORE》（忘了哪个在后面了）。高中这么忙，又想到反正网上也下得到，后来就不怎么爱出去看电影了。这次突然又想看了，是因为全球同步首映嘛，就好像看体育直播一样，很激动；还有就是不管好不好看，到时候网上出来了也要看看，倒不如现在就看了。网上等会等得很辛苦，从TS到TC再到DVDSCR最后出 DVD要走很长一段路。
    引用某位代表先进生产力的老师说的话，电影《达芬奇密码》有以下两点问题。

1.昏的
    我敢说，如果谁没看过书，后来的几个转折肯定看不懂。有些地方确实没讲清楚，如果不是看了书的话根本不可能知道。所以说，整个后半场都是昏的。
2.对教材不熟
    电影算比较忠实原著，但还是有许多地方省略了。比如大小两个密码筒，外面那一个字母映射的“SOFIA”密码省了；还有诸如输入1123581321时 “撤消”等情节也没了。有些地方，我可以说它结果相同，也可以说它结果不同。所以说，拍这类电影应该搞教材，搞笔记，要把教材玩弄于骨掌之间。


回留言：
    呵呵，我不是这个意思，在留言里败坏我形象的当然不是说的你们，是怕尚猫等留些言说“……………………（省略）”让别人看。
    显然达芬奇密码不可能和THE MATRIX比，甚至可以说达芬奇密码的电影完全失败了。这么精彩的小说完全可以拍得更好，就像指环王一样可以创造一个小说改编电影的奇迹。

    最早提出“政治科幻”一词的人肯定是个强人。这四个字充分地体现了V For Vendetta的全部特点。政治科幻，一种与未来的政治体制有关的科学幻想。从这里看到的，不过是无数历史上专制政权的一个影子，和一个戏剧化的追求自由的人。
    V For Vendetta是那种越看越激动的电影。看到最后的烟花，我简直快哭出来了。这是一种看到最高政权一夜间被颠覆的快感，大概下个星期看24大结局时看到预告片里Jack掏出枪指着总统说You have to face justice时就是这个感觉吧。每个有权利的机构多少都有些让人作呕，正如推翻第八监狱的统治是学生的愿望。我没事经常在想如何抓住某个学生和老师的矛盾，煽动一下群众，然后大家一起来造反。“V”就是一个很会做这些事的人。他用了20年的时间，精心策划了一次没有任何漏洞的计划来推翻当时的专制政权。在电影中，“V”并不是一个不死的神；他是一个人，他最后还是死了。但是，他在电影中反派人物面前总是一个神秘的、戴着面具的、刀枪不如的人。而这样已经足够让人们记住一个不死的象征：他在某一年的11月5日出现了，并许下诺言；然后在第二年的11月5日再次出现，完成了他的使命，从此消失。正如我看了电影后见人就说的，电影中有一幕十分精彩：政府里某人（忘了叫啥了）对着“V”连开数枪，然后问他为什么不死，他说，这个面具之下不是肉体之身，是一种思想；而思想是不怕子弹的。

    早以前就想，18岁生日那天一定要干一件惊天动地的大事。然而，真到了这一天，就这么平淡地过了也不觉得有多惊讶。2点半睡觉，7点半起床，上课，做作业，历史听写，一集Numb3rs，一集24，然后又2点半睡觉。
    现在感觉基本上“生日”的概念已经被淡化了，什么特别的事也没做。和平常不同的，不过是帮小方的爸爸做了个课件。
    还有呢，就是到教室时发现桌子上有一颗糖，也不知道是不是谁给我的，我抓起来就吃了。是我哪个MSN好友做的好事或是知道谁做的好事，请在下面留个名。
    还有一个，尚猫欺负我，又把我手表藏哪里去了~~~~

补两句注释
    //完了完了完了完了，一个星期没上MSN Space，竟然就发生了剧变——这个MSN Space被一中的发现了
    //又考虑到加了些Vijos的好友和其他乱七遭八的人，因此，大家留言的时候不要败坏我天使般纯洁的形象

    对于一个倒像不像的数学体系，歌德尔不完备定理同样适用。它告诉我们，一个哲学体系永远不可能证明自己是完备的。而这一点体现在马克思主义哲学上是更显然的。运用马克思主义哲学的理论绝对不可能证明马克思主义哲学本身是正确。换句话说，一个合理的哲学体系在理论上被证明了是不存在的。
    对以上观点的支持，不同的人会拿出不同的武器。嘎嘎将会郑重地抬出“人择原理”来。人择原理的内容我很早就知道，第一次听说它叫做人择原理还是在车站和嘎嘎讨论唯X主义的时候。后来感觉到，人择原理运用到哲学上将产生一种非常奇特的滑稽效果。
    那么我们为什么还要学习哲学呢？原因很简单，因为我们要考试。好在答题时我们不用考虑马克思主义哲学的正确性。仿佛考试时会假定，马克思主义哲学的所有理论都是正确的。如果谁高考时能答出一个“由此可见，马克思主义哲学具有局限性”的话，他肯定是个疯子。
    正如前几天跟NK和幸兄说的那样，做到一道题要判断“坚持集体主义是个人生存和发展的必要条件”是否正确时，我想，没有那么严重吧。翻答案，这句话是正确的，要选。于是，我再一次明白，以后看到像“工业反哺农业是解决三农问题的重大突破”、“要毫不利己，专门利人”之类的话都当作正确来处理。
    最后一例，突出地表现出政治学习的悲哀。
    半期考了一道题，选择，问区域发展有利于整个国家经济发展的哲学依据。这道题的答案显然是错误的，但即使答案错了，石X也可以找到另一种不算牵强的解释。后来我去找她分析卷子（事实上是她要我找她去分析卷子），我和她说起这个题时我说，这道题答案显然是错的，这点自信一定要有，但是我不想跟你争，争起没意思。她气得鬼火冒。我说，好，争嘛争嘛。于是就争了十几分钟。当然最后没有争出结果。我也拒绝承认她的观点。有时候啊，文科的题争起真的没有意思，都有道理，选哪个是萝卜和青菜的关系。但是如果真的要争起来，你是不能屈服的。因为你没有错。在大家都没有错的时候，比的是谁更有气势，谁更有权威。分析卷子时尚猫在我前面，我听她的意思貌似这题本来也想争一下，但一开始在气势上就败了下来。我打赌猫现在也觉得这题有问题，但搞文科的就是这样，拿个题去问老师，老师说，是这样这样（而且知道她会这么说），然后回答，哦，哦，然后就走了。其实自己心里还是觉得自己是对的。所以我从来就没问过老师任何问题。这次不同，和石某说到了，不讨论不行了。于是我走起来第一句话就是，这题答案肯定是错的，绝对该选某某。这话一说，两种完全对立的观点陡然耸立，十分钟后势必两败俱伤。石某陷得很深，不能自拔。如此简单的道理她都没看穿，这么简单的道理我已经说得不能再清楚了。估计她也急，她也觉得为什么这么简单的道理我不明白。发展到最后的结果，双方都不可能更进一步地说明了。最后我跟她说，五一写篇千字论文来说服她。
    废时间写什么论文也确实不必，在这里顺带着说一下就行了。写个政治论文的时间，USACO都做了一章了。
    争论的焦点在整体和部分的关系上。她认为该选整体，因为题目“区域发展有利于整个国家经济发展”的后半句是整体方面。其实，这个随便怎么说都是强调部分。下来后我想到了一个更幼稚的解释。哲学依据就是找原因。A有利于B的原因肯定是A很好，而不是B很好。经常做爱可以锻炼身体是因为做爱的运动量很大而不是身体壮了可以打台湾。


    noi.cn消息：第23届全国青少年信息学奥林匹克竞赛7月22日至28日在绵阳南山中学举行。
    拿到传说中的八中作文选，看到了曾经的她的作品。她交的这篇还是我给她打的。
    看《数据结构与算法分析》时想起我的一个（半真半假的）故事，有空写。