堆排序和换座位的故事(heap sort)

说的是现在刚开学,小敏的班主任为了让大家好好学习,决定根据上学期期末考试的分数给各组重新编排位子。

小敏所在组一共有5个人,从讲台方向算起分别是第0位:考了70分的小敏,第1位:满分100的学神小然,第2位:考了60分的学弱老何,第3位:考了95分的学霸尧哥,和第4位:只考了20分的学渣小龙。

hs1

班主任采用的是“堆座位”,即某人假如某人座位号是i,后排同桌左边那一位座位号就是(2i+1)后排右边那一位就是(2i+2)。也就是说,小敏的座位号是1,没有同桌(谁叫她上课爱讲话)小敏的后排是学神小然和学弱老何。由于采用的是“堆座位”,所以老何的后排没人,但小然的后排却有学霸尧哥和学渣小龙。班主任知道老何一点也不喜欢这种排序方式——他上课不能靠着椅子睡觉了。

然而这种排序方式带来很不好的影响,由于每次学霸遇到试卷,都会发出耀眼的光芒而释放出答案,而学渣只产生烧焦羽毛味的气体,这两种现象可能会相互干扰,所以得让学霸尽量坐后面而学渣尽量坐前面,以免学渣上课不专心。事实上,上学期每次考试结束,班主任批改试卷时偷偷看小敏的小组后面的两排,同桌左右都是冰火两重天!

班主任现在开始排序。班主任决定先把学霸按分数依次移到前面来,然后和位于最后的人交换位置就行了。座位号最大的有后排同学的人开始。小然的后排有尧哥和小龙,很显然,每次考前尧哥都在查漏补缺,而小龙都在女娲补天。虽然尧哥成绩要比小龙好很多,但还是没有考前一直看漫画的小然成绩好。所以对于这三个人,暂时是不用换的。第一轮“创建最大堆座位”的第一部分也就结束了。

位于小然编号前面的是小敏,小敏的后排有小然和老何。小然和老何都是喜欢看科技类漫画杂志的,例如《科幻世界》什么的,班主任是很清楚的——办公室都不知道缴了多少本了,可他俩依然照看不误。不让小然和老何做同桌,或许能阻止他俩上课交换漫画看。另外,小然的分数比老何高,也比小敏高,那么就让小敏和小然交换位置。小敏成了小然的坐后排,小敏也有了同桌——老何,真希望他俩上课不要讲话!

但这时还没完,小敏的后排仍有可能比她分数大的需要调换位置。事实上,尧哥的分数确实比小敏要高,那么小敏还得和尧哥换次位置。这可苦了小敏,她刚坐下又得站起来继续调换位置。终于,第一轮“创建最大堆座位”的第二部分也结束了。座位第一次成为了“最大堆座位”。

hp2

现在小然坐在最前面,现在得让她和最后面的同学调换位置,那么小然就能安心刷题(事实上是看漫画)了。之后小然的座位就固定了,就不再需要参与到换位置的事情中,而其它同学继续换。座位就成了这样。

hp3

交换完后继续第二轮“创建最大堆座位”。不过这次不同,先从最前面的有后排同学的开始选起。小龙的后面是尧哥和老何。班主任已经从小龙的眼神中读出来什么:“把我编的最前面,我以后还上课还怎么睡觉,看小说?”小龙其实挺聪明的,可就是不肯好好学习,说什么“应试教育扼杀创造力”之类的。班主任发现其实可以对小龙来个七擒七纵。

尧哥的分数比他的同桌老何要高,也比他的前排小龙要高,自然又和小龙调换位置。不过这样小龙的后排的分数依然有可能比小龙高。正是这样,于是小敏又和小龙换了一次座位。小敏换了三次座位,累的气喘吁吁。

hp4

第二轮“创建最大堆座位”结束,最前排的尧哥和最后排的小龙再次调换座位,这样尧哥的位置也固定了下来。这样尧哥就能专心刷他的X年高考N年模拟了。然而小龙再次做到了前排。班主任从小龙的眼神中读出了惊恐:“我怎么又到了前排?”班主任只是笑笑,不说话,其实班主任很喜欢《三国演义》中的诸葛孔明的。

hp5

那么继续第三轮“创建最大堆座位”。小敏的分数比他目前的同桌老何要高,也比他的前排小龙要高。那么小敏继续和小龙交换位置。小敏这四次搬座位已经快把她累的趴下了,不过这也不能怪小敏体质不行,谁叫体育老师总是请假呢?

第三轮“创建最大堆座位”结束,班主任注意到老何在偷笑——他一次座位也没换,坐在那儿舒服极了!不过嘿嘿,现在就轮到你了!现在需要固定小敏的位置,小敏和老何又调换一次位置。小敏生无可恋地趴在课桌上。

hp7

开始第四轮“创建最大堆座位”,不过,现在老何已经比他的后排小龙分数高了,因此现在已经是“最大堆座位“了。现在该固定老何的位置了。老何再次和小龙交换位置,小龙又再次到了前排。班主任好歹也算“三擒两纵”了小龙。老何继续看他的漫画书。

现在只剩小龙一个人座位没固定了,事实上也没人能和他换了,于是小龙坐到教室后面看小说睡觉的想法只好不了了之。现在小敏这组的座位就已经按分数从低到高全部排好了。

hp8

班主任终于在大课间下课铃响之前把全班同学的座位排好了。“那么好,同学们,我们现在开始考试”。

Leave a Reply