索引堆插入

Question

如果先insert(0,e1),再insert(100,e1)这样（数组中只插入了这两个元素），怎么建堆了？

Answer 1

liuyubobobo 2017-08-30 00:40:58

我们的堆在面对相同的元素的时候，不会进行shiftUp操作，所以只有这两个相同元素时，形成的堆是这个样子哦：

   1  （外部索引从0开始，我们的实现插入索引堆后索引从1开始）
  /
101

要注意，索引堆只是索引排列成堆的形态（对应我们的实现代码中的indexes数组），但是具体的数据内容依然在他们自己的索引位置（对应我们的实现代码中的data数组）。如果对这一点理解的不够透彻，建议先继续往下看，在我们学习图的最小生成树和最短路径算法时，都会使用索引堆进行优化。到时候结合索引堆的具体应用，或许会理解的更透彻哦：）

这个课程的所有代码都可以再课程的github中找到。也可以自己亲自用具体的例子实验一下哦：）

https://github.com/liuyubobobo/Play-with-Algorithms

• 提问者 CHZone #1

  我表述有误。普通堆插入元素时，在数组的末尾追加元素，而索引堆插入时需指定插入的位置，如果指定的插入位置使得数组中元素存储的位置不连续（例如:先insert(0,e1),再insert(100,e2)，0~100之间的元素还未插入），会不会导致建堆失败。我对索引堆在插入时需定位置这个变化有点疑惑，为什么不直接追加元素呢？

• liuyubobobo 回复 提问者 CHZone #2

  可以参考这个问答：http://coding.imooc.com/learn/questiondetail/14784.html

• liuyubobobo 回复 提问者 CHZone #3

  http://coding.imooc.com/learn/questiondetail/4945.html

点开查看后面3条评论