有一组数据（15,9,7,8,20,-1,7,4）,用堆排序的筛选方法建立的初始堆为（）筛选方法是什么?好纠结呜呜选项a．-1,4,8,9,20,7,15,7b．-1,7,15,7,4,8,20,9c．-1,4,7,8,20,15,7,9d．a,b,c均不对.

Question

有一组数据（15,9,7,8,20,-1,7,4）,用堆排序的筛选方法建立的初始堆为 （ ）
筛选方法是什么?好纠结 呜呜
选项
a．-1,4,8,9,20,7,15,7 b．-1,7,15,7,4,8,20,9
c．-1,4,7,8,20,15,7,9 d．a,b,c均不对.

Answer 1

如果你的问题是递减排序,就需要首先建立一个小根堆
因为其中有重复的关键字,因此当左右孩子相等并且需要和双亲调整时,原则上无论左右哪一个都可以,所以实际上这个问题会出现两个答案：
-1, 4, 7, 8, 20, 15, 7, 9 和-1, 4, 7, 8, 20, 7, 15, 9
一般算法都是和左子树的调整,这时就是前面的答案了

如果你的问题是递增排序,就需要先建立一个大根堆,不过这时只有唯一的答案：
20, 15, 7, 8, 9, -1, 7, 4