索引堆插入方法

Question

这个insert方法，i好像不需要用户传入，insert方法设计从接口上来说也不应该让用户传入i

Answer 1

liuyubobobo 2021-06-28 17:18:46

不是的，对于索引堆来说，是需要索引的，否则和普通的堆是没有区别的。

可以参考这里：https://coding.imooc.com/learn/questiondetail/AKpB2PJAg0y6bv0E.html

继续加油！：）

• _江湖郎中 #1

  老师，为什么在指定位置i插入元素，不需要先移动后面的元素呢，感觉位置i的元素会被覆盖。

• liuyubobobo 回复 _江湖郎中 #2

  在索引堆中，每一个索引只能有一个元素。所以在一个索引 i 上，不能插入两个元素，但是可以随时修改索引 i 位置的元素。
  
  正是这个原因，你可以看到，在我们最终完成的索引堆中：https://git.imooc.com/coding-71/coding-71/src/master/04-Heap/Course%20Code%20%28C++%29/09-Index-Heap-Advance/main.cpp
  
  85 行要判断，当调用 add 的时候，索引 i 应该没有元素；
  如果要修改索引 i 的元素，可以调用 155 行的 change 方法。
  
  你之所以提出这个问题，是对索引堆的应用场景不了解。这很正常，在这一小节，我们没有介绍索引岁的应用场景。在这个课程的后续的图论算法部分，你会看到对索引堆的应用，就会明白索引堆为什么这么设计了。在这个问答下，我简单描述了一些索引堆的应用场景，请再体会一下，索引堆的索引是有语义的，不是简单的“在数组中排第几个”而已：https://coding.imooc.com/learn/questiondetail/99784.html
  
  继续加油！：）