有关contain函数的实现

Question

您在视频中说道，在修改（change函数）或者获取某个索引的元素（getItem）时，要先判断，这个索引指向的位置是否真的存在元素。而且，判断条件不能简单的判断索引是否小于capacity。

我的问题是，判断条件能不能是索引小于count + 1呢？因为count表示的是当前堆中实际存在的元素个数。

Answer 1

音视频雪兔 2021-06-22 08:18:31

看了老师的答案，我再说一下自己的理解。索引堆是一个容器，里面会存放数据。而数据存放在data容器中。对于data容器，索引i的数据datai肯定存在于容器data中，但是datai可能还没有插入到索引堆中。例如堆的容量远远小于data容量的情况。这个就是优先队列的应用，data中的数据是逐步放入堆中，然后按照优先级取出。这种情况，索引i的数据，肯定在data中，但有可能不在堆中，所以用i<=count+1判断contain并不准确。

Answer 2

liuyubobobo 2019-02-24 07:15:23

不可以。

索引堆中，索引和数据的数量没有必然联系。我们可以直接将一个索引为100的元素插入索引堆，但是这个索引堆中只有1个元素：）

可以参考这个问答，看看能不能更理解索引堆的应用场景和设计意图：https://coding.imooc.com/learn/questiondetail/99784.html

在这个课程后续，我们会具体使用索引堆，解决算法问题的：）

继续加油：）

• 提问者 血色星期二 #1

  那我还有疑问是，change 函数和 getItem 函数的参数 i ，也就是外部传入的索引值是否一定是从0开始的连续整数呢？因为，像您举得例子，比如，系统的进程ID，通常都不是连续，再比如学号，也不是连续的。
  
  那在这种情况下，既然 i 和数据的数量没有必然联系，怎么能将 i 和 capacity 进行比较呢，也就是像 contain 函数中一开始进行比较的那样？比如，想创建一个 capacity 为100的索引堆，但是第一个学生的id是1000，那这直接就超出容量了。
  
  所以，我的问题是，既然 外部传入的索引 i 和数据的数量没有直接联系的情况下，又怎能直接和 capacity 进行比较呢？

• liuyubobobo 回复 提问者 血色星期二 #2

  1）此时id不是索引，而是数值。id存储在一个数组中，它在数组中的索引是0：）2）对于我们的索引堆来说，其实是没有capacity这个概念的，我们的索引堆无法添加元素（这点和堆不一样，当然，我们可以把它改进为可以添加元素的索引堆，但是这个数据结构更复杂，不再这个课程的范畴了），对于索引堆的使用，在后续图论中，我们就会看到具体的应用场景，届时，结合具体应用，可能将更能理解我们设计的索引堆的意图：）