有关contain函数的实现

来源：4-9 索引堆的优化

血色星期二

2019-02-23

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

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

写回答

2回答

音视频雪兔

2021-06-22

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

liuyubobobo

2019-02-24

不可以。

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

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

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

继续加油：）

liuyubobobo

血色星期二

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

2019-02-24

共2条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

查看课程

相似问题

contains函数实现问题

回答 1

不能将函数模板“void selectionSort(T [],int)”用作函数参数

回答 3

传入函数指针作为参数啥意思呢老师

回答 1

关于顺序查找的函数设计问题

回答 1

老师我想用链表实现二叉堆,在交换元素这步卡了好久,能提供java版的代码以及思路吗!谢谢

回答 1

打开慕课网App查看更多内容