对最大索引堆的第i个索引值的修改方法的疑问

Question

老师程序里面的方法注释：“将最大索引堆中索引为i的元素修改为newItem”跟我理解的不一样。我的理解是：索引i是针对一个最大堆而言的，最大堆的索引是从1开始的，我觉得这个change方法应该是对最大堆从第1个索引开始的第i个索引对应值的修改，而不应该是对data里面的第i个索引对应值的修改，因为堆对象的data数组的元素在此之前一直没有改变，一般情况下不满足最大堆的性质，如果直接data[i+1]=newValue，我觉得跟注释所表达的意思不一致吧。
按照老师的注释意义，我觉的应该是这个意思？
public void change(int i, Item newValue) {
datas[indexes[i]] = newValue;
shiftUp(i);
shiftDown(i);
}

Answer 1

liuyubobobo 2019-01-29 03:04:00

虽然可以按照你思考的语义设计一个函数（我看到你已经写出来了，大赞：））不过，关键是，索引堆一般不是这么使用的：）

之所以设计索引堆，是因为索引是一个外部信息。是不随堆中的数据码放方式来改变的。

比如，每个学生有学号，有成绩。学号就是索引。我们可以根据学生的学习成绩建立出索引堆。但是，在修改的时候，通常的业务场景是：我们要修改指定学号的学生成绩（即修改指定索引的值），而不是修改堆中第几个元素的成绩。因为，此时，你根本不知道堆中第i个元素是哪个学生的成绩，在业务层面，根本没有这个需求：）

或者换个角度思考：如果我们是要修改堆中排在第i个位置的元素，其实根本不需要建立索引堆。因为索引就隐含在data的索引上：）

再比如，操作系统里，每个进程有进程ID和优先级。进程ID就是索引。我们可以根据进程的优先级建立出索引堆。但是，在修改的时候，通常的业务场景是：我们要修改指定进程ID的优先级（即修改指定索引的值）。请再体会一下：我们通常的业务场景，索引是一个外部的固定信息，和堆中数据的码放方式是没有关系的：）

不过在这里，确实：我只是给除了索引堆的实现，还没有看到索引堆的应用，所以很多同学可能不理解索引堆这样设计的原因。在这个课程的后续，无论是Prim最小生成树，还是Dijkstra最短路径，都会是用索引堆，届时，可能同学们就能更加深刻的理解索引堆的使用。在回头看这个问题，就明晰了：）

加油！：）

• 提问者 慕粉3169703 #1

  非常感谢！