Algs4-2.4.26无需交换的堆

2.4.26无需交换的堆。因为sink()和swim()中都用到了初级函数exch(),所以所有元素都被加载并存储了一次。回避这种低效方式,用插入排序给出新的实现(请见练习2.1.25)。

答:以小堆swim为例,如下图所示:

1)元素1与4对比,再与4互换位置;
2)元素1与3对比,再与3互换位置;
3)元素1与2对比,再与2互换位置;
每一次exch互换位置需要三次赋值操作。

如果改用插入排序使用的新方式步骤如下:
1)复制元素1
2)元素1与4对比,把4复制到1的位置。
3)元素1与3对比,把3复制到原4放置的位置。
4)元素1再2对比,把2复制到原3放置的位置。
5)元素1放置原2放置的位置。
每一次放置只需要一次赋值操作。





原文地址:https://www.cnblogs.com/longjin2018/p/11440169.html