Question

一道数据结构题

为啥建立大顶堆，才会堆排序是非递减序列？那小顶堆呢，实在不理解，谢谢指点

Answer 1

何为索引堆？
索引堆是对堆进行了优化。
优化了什么？
在堆中，构建堆、插入、删除过程都需要大量的交换操作。在之前的实现中，进行交换操作是直接交换datas数组中两个元素。而索引堆交换的是这两个元素的索引，而不是直接交换元素。
有什么好处？
主要有两个好处：
减小交换操作的消耗，尤其是对于元素交换需要很多资源的对象来说，比如大字符串。
可以根据原位置找到元素，即便这个元素已经换了位置。
如何做到的？
索引堆使用了一个新的int类型的数组，用于存放索引信息。部分代码如下：
// 属性 $data = array();// 存放数据的数组 datas[1..n] $indexes = array(); // 索引数组
这里这个indexes数组，存放的是什么信息呢？它是如何工作的呢？假如我们有这样一个最小堆：
paste
那么用数组表示就是：
datas: [-, 1, 15, 20, 34, 7]
现在要维护最小堆的有序性，就需要交换15和7这两个元素。交换之后的元素数组是：
datas: [-, 1, 7, 20, 34, 15]
而此时，我们再想找到原来在datas[2]位置的元素，已经找不到了。因为此时data[2]已经换成了7，而系统并没有记录15被换到了什么地方。
可不可以既保持$data的原始特性（读取O(1))想要得到i位置的元素，直接datas[i]就可以了, 也保持堆的特性。可以的，使用索引堆。
使用索引堆
使用索引堆后，初始化两个数组应该是这样的：
$datas: [-, 1, 15, 20, 34, 7] $indexes: [-, 1, 2, 3, 4, 5]
这个时候，我们就交换indexes数组里面的索引2和5，而不操作datas数组。交换后两个数组是这个样子：
$datas: [-, 1, 15, 20, 34, 7] $indexes: [-, 1, 5, 3, 4, 2]
这个时候，想要得到i位置的元素，就需要$datas[$indexes[i]]来获取。