关于索引堆的删除问题
来源：4-8 索引堆(Index Heap)
易萧
2017-06-08
count--实际上表示的是索引被删除吧。索引的个数虽然少了，但是这个索引可能指向data的任何一个位置，假设是data[2]，那么之后就没有了2这个索引，数组的值仍然没有改变，如果一直往数组后添加数据，就会使得索引未满，但数据却占满了，如果移除这个元素，又会导致需要更新很多其它的索引。这或许是插入的时候使用传入的i，可以对被删除的索引相对应的data单元重新索引？？不过，用户又怎么知道数组中间哪些数据是被删除的呢。
写回答
1回答
-
我们所构造的索引堆，是不能向数组data的后面添加新的元素的，可以观察一下整个代码，会发现我们的索引堆最多只能容纳在构造的时候capacity个元素。
很能理解你在这里对索引堆产生的疑问。其实你高估了我们建立的这个索引堆的灵活度。我们的这个索引堆在具体构建的时候抛除了具体的应用场景，所以会让你觉得似乎有些操作是无法完成的。实际在使用索引堆的时候，索引堆外面是必须有一个数据数组来配合。索引堆的目的只是为了快速的找到所有数据中的最大值或者最小值，或者在外面的数据有更新的情况下，整个索引堆也快速进行相应调整，用户获取具体的数据信息，是靠外面的数据，而不应该通过索引堆。
对于索引堆的具体应用，我们在这个课程后续的图相关算法中，无论是最小生成树的Prim算法，还是最短路径的Dijkstra算法，都进行了使用。不妨在这里先对索引堆这种数据结构有一个简单的印象，在后续结合这两个算法中索引堆的具体应用，会对索引堆有更深刻的认识的：）
042017-06-10
相似问题