索引最大堆中的insert()方法

Question

1 2 3 4 5 6 7 8 9

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中没有对其进行相应的处理？

Answer 1

liuyubobobo 2018-01-24 08:51:47

在我们的索引堆中，是不能在相同索引的位置前后insert两次item的，所以在下一小节的代码中，我们会在insert前多加一个assert，如下（注意有注释的那一行assert）：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

// 向最大索引堆中插入一个新的元素, 新元素的索引为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索引的位置是有元素的：））

1 2 3 4 5 6 7 8 9 10 11

// 将最大索引堆中索引为i的元素修改为newItem     void change( int i , Item newItem ){               assert( contain(i) );               i += 1;         data[i] = newItem;              shiftUp( reverse[i] );         shiftDown( reverse[i] );     }

以上代码都取自下一小节，这一章彻底讲完索引堆后的最终代码：）