关于索引堆里的change函数

Question

data数组里的元素有可能不是连续的。如果我们传入的下标i在data[i]里面就是空着的，我们让它data[i] = newitem。那change函数里面for循环寻找indexes数组里面的元素为i的过程那就有可能运行不了 并且 变成非最大索引堆。
我自己想到了一个解决办法，不知道这样可不可行`

void change(int i, Item newitem)
	{
		//判断data[i]是否有值
		if (data[i] != NULL)
			data[i] = newitem;
		else
			return cout << "该位置没有insert元素" << endl;
		for (int j = 0; j < count; j++)
		{

			if (indexes[j] == i)
			{
				shiftdown(j);
				shiftup(j);
				return;
			}
		}
	}`

Answer 1

liuyubobobo 2023-01-05 14:23:34

我不确定我是不是理解了你的问题。但是，对于索引堆来说，如果 data[i] 里没有元素，就不能调用 change 操作。因此在这一小节，我加入了  157 行的断言：https://git.imooc.com/coding-71/coding-71/src/master/04-Heap/Course%20Code%20%28C++%29/09-Index-Heap-Advance/main.cpp

这是数据结构本身的限制。（就像堆只能去堆顶元素，不能取其他位置的元素；栈只能访问栈顶元素，不能访问其他元素一样）。

至于索引堆为什么这么设计，在这一小节，我确实没有使用具体的实例来介绍索引堆的应用场景。关于索引堆的应用场，在课程后续的 mst 和 dijkstra 算法中都有应用，解释可以再做体会。也可以参考这个问答：https://coding.imooc.com/learn/questiondetail/99784.html

继续加油！：）