索引最大堆中的insert()方法
来源：4-8 索引堆(Index Heap)
想不出来叫什么
2018-01-24
public void insert(int i, Item item){
assert count + 1 <= capacity;
assert i + 1 >= 1 && i + 1 <= capacity;
i += 1;
data[i] = item;
indexes[count+1] = i;
count ++;
shiftUp(count);
}老师您好！索引最大堆中，insert方法是把data[i+1]替换为item，那么indexes[]中所存放的i+1所代表的元素不是就变了吗？为什么在 insert中没有对其进行相应的处理？
写回答
1回答
-
在我们的索引堆中，是不能在相同索引的位置前后insert两次item的，所以在下一小节的代码中，我们会在insert前多加一个assert，如下（注意有注释的那一行assert）：
// 向最大索引堆中插入一个新的元素, 新元素的索引为i, 元素为item // 传入的i对用户而言,是从0索引的 void insert(int i, Item item){ assert( count + 1 <= capacity ); assert( i + 1 >= 1 && i + 1 <= capacity ); // 再插入一个新元素前,还需要保证索引i所在的位置是没有元素的。 assert( !contain(i) ); i += 1; data[i] = item; indexes[count+1] = i; reverse[i] = count+1; count++; shiftUp(count); }如果想修改某个索引的元素，不应该使用inser方法，而应该使用change方法。这也正是索引堆的一个优势——可以随时修改堆内的任意元素，代码如下：（注意我们先使用assert(contain(i))确保了i索引的位置是有元素的：））
// 将最大索引堆中索引为i的元素修改为newItem void change( int i , Item newItem ){ assert( contain(i) ); i += 1; data[i] = newItem; shiftUp( reverse[i] ); shiftDown( reverse[i] ); }以上代码都取自下一小节，这一章彻底讲完索引堆后的最终代码：）
20
相似问题