关于索引堆的删除问题

Question

count--实际上表示的是索引被删除吧。索引的个数虽然少了，但是这个索引可能指向data的任何一个位置，假设是data[2]，那么之后就没有了2这个索引，数组的值仍然没有改变，如果一直往数组后添加数据，就会使得索引未满，但数据却占满了，如果移除这个元素，又会导致需要更新很多其它的索引。这或许是插入的时候使用传入的i，可以对被删除的索引相对应的data单元重新索引？？不过，用户又怎么知道数组中间哪些数据是被删除的呢。

Answer 1

liuyubobobo 2017-06-09 01:29:10

我们所构造的索引堆，是不能向数组data的后面添加新的元素的，可以观察一下整个代码，会发现我们的索引堆最多只能容纳在构造的时候capacity个元素。

很能理解你在这里对索引堆产生的疑问。其实你高估了我们建立的这个索引堆的灵活度。我们的这个索引堆在具体构建的时候抛除了具体的应用场景，所以会让你觉得似乎有些操作是无法完成的。实际在使用索引堆的时候，索引堆外面是必须有一个数据数组来配合。索引堆的目的只是为了快速的找到所有数据中的最大值或者最小值，或者在外面的数据有更新的情况下，整个索引堆也快速进行相应调整，用户获取具体的数据信息，是靠外面的数据，而不应该通过索引堆。

对于索引堆的具体应用，我们在这个课程后续的图相关算法中，无论是最小生成树的Prim算法，还是最短路径的Dijkstra算法，都进行了使用。不妨在这里先对索引堆这种数据结构有一个简单的印象，在后续结合这两个算法中索引堆的具体应用，会对索引堆有更深刻的认识的：）

• 提问者 易萧 #1

  ？？不能添加新元素？那insert函数是干嘛的？用户可以指定在索引为i的地方添加元素啊。

• liuyubobobo 回复 提问者 易萧 #2

  不是不能添加新的元素，是最多只能添加capacity这么多的元素。索引堆中的data是无法扩充的。添加新元素的方式不是在data后面append新的元素，而是为data[i]赋值。

• liuyubobobo 回复 提问者 易萧 #3

  当然，可以改进索引堆，让它突破这个限制。不过在后续课程中，你会看到，我们这样的索引堆，已经可以非常好的用来优化Prim算法和Dijkstra算法了：）

点开查看后面1条评论