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