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

Question

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）：

// 向最大索引堆中插入一个新的元素, 新元素的索引为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] );    
}

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