http://data.biancheng.net/view/79.html
数字代表段的长度,带权路径长度与硬盘读取开销成正比
上图中的归并过程需要对外存进行读/写的次数为:(9+30+12+18+3+17+2+6+24)*2*2=484
(图中涉及到了两次归并,对外存的读和写各进行 2 次)
对于如何减少访问外存的次数的问题,就等同于考虑如何使 k-路归并所构成的 k 叉树的带权路径长度最短。
构造一棵赫夫曼树作为归并树:
image.png(2*3+3*3+6*3+9*2+12*2+17*2+18*2+24*2+30)*2=446
附加“虚段”的归并树
若 9 个初始归并段改为 8 个,在做 3-路平衡归并的时候就需要有一个结点的度为 2。
image.png- 注意:虚段的设置只是为了方便构建赫夫曼树,在构建完成后虚段自动去掉即可。
对于如何判断是否需要增加虚段,以及增加多少虚段的问题,有以下结论直接套用即可:
在一般情况下,对于 k–路平衡归并来说,若 (m-1)MOD(k-1)=0,则不需要增加虚段;否则需附加 k-(m-1)MOD(k-1)-1 个虚段。
网友评论