Heap Algorithm

Heap is a binary tree where the max element is always at the root.  Heap is usually implemented by using an array where:

  • Root is at element index 0.
  • A node’s two children is at indices 2i +1 and 2i+2.
  • A node’s parent is at index i/2.

Insert a new element can be done by appending it to the end of the array then do a “SIFT UP” operation to restore the heap. To remove the largest element can be done by removing the element at index 0, move the last element of the array to the index 0, then do a “SIFT DOWN” operation.

Heap is useful in many situations, for example:

  • Top N elements from an array.
  • K-way merging
  • Sorting.

The power of heap comes from the point where it finds max element avoid doing the comparison with all other elements again, instead, the heap structure keeps some comparison result so the new element’s position can be decided in less time.

白白折腾了一番

前一阵子一时兴起,想要用现有自己的电脑和设备,打造一个家庭影院。反正电视音响都是现成的,只需要一个能够播放节目源的 HTPC 就好啦。不过自己很小气,舍不得买一部新的电脑,结果就用以前公司发的 Chromebook 作为替代。Chromebook 一切都好,就是每次操作的时候要跑到电脑跟前,有些不方便。想来想去,后来自己就搞了一个Chromecast,反正很便宜。这样手机拿在手里,直接在选好节目,然后在chromecast上就可以开始播放。这样搞了一阵子,发现还是有些不方便,因为有些节目源不支持cast。折腾来折腾去,后来突然想到干脆搞一套遥控的键盘和鼠标,这样不就可以远程操作我的chromebook了吗?一念即此我就又把以前买苹果电脑 IMac 附带的无线键盘和鼠标拿出来,擦掉灰装上电池开始使用。键盘倒是很快就设好了,可是鼠标怎么也不工作。搞来搞去,最后上网一查,发现老款的苹果无线鼠标,质量就是差,很容易掉线。按照网上很多人的攻略,我给鼠标的电池仓里垫了一些纸,结果也没有完全修好。最后一咬牙,干脆花十块钱买了一个新的无线鼠标。心想这下子问题该全部解决了吧。嘿嘿,我没有想到,现在的无线鼠标需要占用一个USB A接口,但是接了这个USB以后,我的chromebook就连不了功放了。郁闷了一个小时,最后发现。我以前买过一个 HDMI spliter, 这个设备可以在一个接口上同时连接功放和电视,这样省下来的USB A接口就可以连接无线鼠标啦。

折腾了这么久,终于把设备全部都设置好了。可是除了头一天刚设好的时候,兴趣盎然,玩了很久以外,接下来的两个星期根本没有碰过这套设备。看着一大堆东西,杂七杂八的堆在电视旁边,自己觉得很不爽。仔细考虑之下,我就又把chromebook,HDMI split 还有无线鼠标等等全部又都收拾起来了。前后这么折腾了几个星期,重新又回到原点,劳民伤财,费神费力。现有的东西真的已经足够好了,以后再也不能干这些事情啦!

印度的疫情和美国的疫情

最近出了很多新闻报道,都说印度疫情严重,人民水深火热,每天的死亡人数和感染人数屡创新高。我很好奇他们的情况到底有多严重,就去和美国的数据对比了一下,结果惊奇的发现,美国去年年底的疫情比印度要厉害的多,感染人数跟印度差不多,死亡人数甚至超过印度很多。下面是来源于Google的数字

 

印度现在每天感染人数40万。

 

美国今年1月高峰感染人数每天30万。

 

印度现在每天因新冠死亡的人数为4000人。

美国今年2月高峰的时候,新冠每天死亡人数竟然超过5000人。

考虑到美国只有3亿人,而印度有13亿人,按照人口总量来算,美国的疫情显然要严重得多得多,平均到每个人头上,感染和死亡的概率要大好几倍吧。奇怪的是,我当时在美国也没有什么感受,没有看到什么报道说美国人民生活在水深火热之中,难道美国媒体也像大陆媒体一样报喜不报忧?!真是不知道这些新闻媒体报道对于人们的印象竟然产生了这么大的扭曲。

Liona Foyd 的吉他曲 What Child Is This

年轻的时候听一段吉他曲,曲调是《绿袖子》,中间有一段变奏自己很喜欢,但是却从来没有搞清楚过演奏者是谁。

多少年以后,自己开始学习弹钢琴,最近又重新练习了这首《绿袖子》,顺便又想起来当年听过的吉他曲。奇怪的是,自己在网上找了好几次,从来没有找到过那段曲子。直到今天晚上。自己下定决心,花了整整一个晚上,终于搞明白,这首《绿袖子》曲调还用来做了一首圣诞颂歌,叫做 What Child Is This。我听到的那个版本是Liona Foyd 的吉他曲 What Child Is This,这段心事总算是了了啊。

换了一个新鼠标

自己的鼠标按的太多了,对食指的损害很大。期间从右手鼠标换成左手鼠标,结果现在两个手的食指都是常年疼痛。所以最近干脆变成了用大拇指按鼠标。我用的那款鼠标有六个按键,设置一下用大拇指按键,倒是很方便。但是奇怪的是,大拇指的那几个键很容易变成 Double Click,很多操作都搞乱了,自己为此苦恼了很久。本来想忍一忍就算了,也许自己年纪见长。忍耐力比以前强了很多吧。但是某一天,我突然想,不能就这样忍下去,为什么不买一个新的看看能不能解决问题?抱着试一试的想法,我买了一个新的鼠标,结果这个鼠标工作完全正常。Double Click再也没有了,我很开心。看来有了问题还是要努力解决,而不是一味忍受啊。

关于废除死刑的另外一个角度

死刑的存在和废除已经引起了很多的争论。自己以往只是觉得人们朴素的复仇愿望应该得到尊重,因此死刑应该保留。直到最近读了一些书以后,对于这个问题突然有了一个全新的角度。人类的科学技术在一直飞速发展中,以战争为例,人类战争的手段从最初的石块,木棒,到后来的刀枪冷兵器,再到后来的热兵器枪炮,再加上后来的坦克,飞机,导弹,直到终极武器原子和氢弹。人类用于杀戮的技术手段进步的速度让人目不暇接。但是能够驾驭这种技术手段的道德水准,却并未得到相应的发展。以牙还牙,以眼还眼,杀人偿命的朴素道德标准依然拥有着极为广泛的群众心理基础。而复仇杀戮这些人类最基本的动机,不可否认和战争有着直接的关系,因此人类社会在大规模战争中完全毁灭的危险毫无疑问是越来越高了。从这个角度出发当务之急是提高人类的道德水准,使之与科学技术的发展水平相适应,否则人类只能最终毁灭于自己发展出来的高超科技。因此从社会的层面上来抑制这些朴素的原始的道德标准,并对之加以引导,就有了它相映的现实意义。试想,如果一个国家的国民都不持有以牙还牙以眼还眼的朴素观念,对于杀人犯只是终身监禁起来。那么这样一个国家,投入相互完全毁灭核战争的危险,也要低很多。这正是本文想要表达的意思。

哪个手的跨度大, 眼睛就去帮助哪个手。

钢琴是一个需要左右手配合的乐器, 常常左右手都有自己独立的旋律进行。自己以前只会把目光集中在左手或者右手上, 而另外一只手就靠摸索了。最近在练习《月光奏鸣曲》的时候, 右手需要大幅度移动的地方很多, 所以我把注意力放在右手上。但是左手有几个和弦的跨度也很大, 只靠摸索很难弹好, 就这样练习了很久都没有什么进步。直到今天才突然意识到, 原来在右手跨度比较小的时候,目光的注意力可以转移到左手上, 这样就可以很轻松的弹好比较大的跨度啦。自己又得到了一个经验。

张爱玲的小说《赤地之恋》和贝多芬的《月光奏鸣曲》

昨天意外地读到了张爱玲的小说《赤地之恋》看完以后心头非常沉重。共产党政权在土改,三反五反等一系列社会运动中暴露出来的摧残人性、泯灭良知、践踏社会公义的恶劣行径,让人震惊。无数美好的事物包括青春和爱情就这样被毁灭掉了。

早上弹起贝多芬的《月光奏鸣曲》,听着柔和的琴声流过,不由得突然痛哭流涕:世间竟然还有这样美好的事物,抚慰一切受伤的心灵,给人间带来至善。愿这美好的事物永存;愿让人的欲望永远限制在人世的规则下,不会过度膨胀而结出恶果。

围棋的三重快乐

前一阵子和朋友聊起天,说到围棋给人带来的快乐。我总结了一下,发现围棋可以给人带来三种快乐。

第一种快乐就是长进水平。这个快乐很纯粹,每个人都能理解。看着自己水平越来越高,当然很高兴。不过长进水平要付出巨大的努力,比如做大量的死活题,或者输了棋以后进行仔细的复盘和反思,不是每个人都能够付出这么大的努力。自己曾经做过几千道围棋死活题,也曾经对自己的对局有过完善的整理,不过终究因为需要付出的努力太大,现在已经完全停止了。相应的,水平长进这个快乐也就没有了。

第二种快乐就是赢棋。这个就像赌博一样,能赢总是让人高兴。另外业余围棋还有一个特点,那就是输了以后,可以再找人下一盘赢回来。即使前面输了好几盘,只要最后一盘赢了,棋友们就可以开开心心的离开了。从这个角度上来讲,业余围棋绝对不能算是一个零和游戏,而是可以让上网下棋的棋友们都高兴。这是职业棋手绝对没有的乐趣,职业棋手输了以后,只能默默地一个人品尝失败的苦果,下一盘复仇的机会还不知道在哪里。值得注意的是,这种乐趣和前面的长进水平实际上是相互矛盾的,长进水平要求下棋深思熟虑,而在网上追求赢棋只会随手下棋,对于长进水平有百害而无一利。赢棋这种乐趣自己现在也还有很多,不过最近也有了一些清醒的认识,希望能够渐渐克服吧。

第三种快乐就是所有的体育比赛都有的快乐,那就是观赏高水平的对抗带来的快乐。现在的围棋比赛讲解很多,YouTube上都能看到。另外围棋世界大赛重量级对决绝大部分都是在中国和韩国之间进行,还有国际国家荣誉的加成。再加上AI的分析,大家对于棋局的理解更加透彻,一局棋下来,业余棋手都可以看出很多门道。所以现在棋迷们观赏比赛,乐此不疲。我也很有兴趣。不过这个和围棋本身关系不大,我有一个朋友。自己不太懂围棋,但是每次围棋世界大赛也要看个热闹。这种乐趣还有一个问题,那就是赢了棋大家高兴。输了棋大家就都郁闷了。这种乐趣自己现在也是沉浸其中,上次lg杯柯洁失利,再加上最近农心杯申真谞连战连胜,真是让人郁闷。回想起以前常昊那个时代,中国围棋被韩国围棋全面压制,很多棋友就再也不看围棋了,看来这种乐趣也有终结的时候啊。

有这三种快乐夹杂在一起,围棋怎么能够说戒就戒掉呢?

画龙添足之调琴师

我的家里昨天来了一个调琴师帮助我调钢琴。他的钢琴调的很快,一个多小时就调好了,而我们家去年来的那个调琴师工作了整整一个下午。反正我也是个菜鸟,看不出来一个人调琴水平的高低,但是无论如何,他调完以后我试了一下,弹起来感觉还不错,总比没有调以前听上去好听多啦,我就高兴的给他付了账。临走的时候,这个调琴师送给我他的名片,上面有他的联系方式,这样我下次想要调琴的时候还可以再找他。我很高兴的接过名片,正要告别,这个调琴师又拿出一张名片,说他还是个房地产经纪人,如果我们想要买卖房子的话,还可以再找他。我当时有些哭笑不得,只好把他的名片接住。我想,调琴怎么说也是一个专业的活,而房地产经纪人也需要很多投入才能做好。一个人又能调琴,又能做房地产经纪人,那他调琴的水平恐怕不会好到哪里。回头跟太太一说,她也哈哈大笑。这个房地产经纪人的名片,真的是画蛇添足啊!