首页 > 其他 > 详细

Algs4-2.4.26无需交换的堆

时间:2019-08-31 21:00:04      阅读:148      评论:0      收藏:0      [点我收藏+]

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放置的位置。
每一次放置只需要一次赋值操作。





Algs4-2.4.26无需交换的堆

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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!