Logic, Analysis, and Computation

宠辱不惊 静观窗前花开花落 去留无意 闲看天上云卷云舒

导航

<2009年5月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

公告

如需转载, 请注明出处。

常用链接

留言簿

随笔分类

随笔档案

文章档案

I/O performance

搜索

最新评论

STL Study Day 8: Ch4. Heap-sort

Heap-sort算法本身没有什么多好讲的,不过, 如何实现它, 其中还是有一些要注意的地方。

第一, 如何设置key, 在CLRS中,是使用的 2i, 2i+1来计算key值, 不过这种方法的局限性很大,如果root为0, 那么它的子节点的key为多少呢?

SGI STL, 使用的是 2i + 1, 和 2i + 2 来设置key的大小, 就避免了上述的问题。

第二, 在pop_heap算法中, 要注意的是: 在左节点key值等于整个数组 (length-1) 的情况下, 该节点不存在, 需要特殊的考虑, 这也是为什么SGI STL在while外, 还要加一个if statement的原因。 刚开始看的这段代码的时候, 迷糊了好一阵子, 后来画了一副图才明白,以后还是不要怕麻烦, 要多画画图。
 
还有, 两个部分, 侯捷这本书就看完了, 继续坚持。

12:25:11 PM Tuesday, May 19, 2009 

posted on 2009-05-20 01:28 小学毕业生 阅读(184) 评论(0)  编辑 收藏 引用 所属分类: STL Study


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理