索引堆插入的问题
来源：4-8 索引堆(Index Heap)
拖车板牙爵士
2017-02-24
如果给索引堆插入新值的时候，如果插入的索引有误，是个固定值，这样就不能形成一个堆了，这种插入相同索引的问题应该怎么解决
maxheap.insert(6,Math.floor(Math.random()*100));
class ImdexMaxHeap {
constructor(){
this.data = [];
this.index = [];
this.reverse = [0];
this.count = 0;
}
size() {
return this.count;
}
isEmpty() {
return this.count === 0;
}
insert(i,item) {//插入元素,传入的i对用户而言，是从0索引的
if(i+1 >=1){
i+=1
}
this.data[this.count+1] = item;
this.index[this.count+1] = i;
this.reverse[i] = this.count+1
this.count++;
this.shiftUp(this.count);
}
shiftUp(k) {
while (k > 1 && this.data[Math.floor(this.index[k]/2)] < this.data[this.index[k]]){
[this.index[Math.floor(k/2)],this.index[k]] = [this.index[k],this.index[Math.floor(k/2)]]
this.reverse[this.index[Math.floor(k/2)]] = Math.floor(k/2)
this.reverse[this.index[k]] = k
k = Math.floor(k / 2);
}
}
shiftDown(k){
while (2*k <= this.count){
let j = 2*k;
if(j+1 <= this.count && this.data[this.index[j+1]] > this.data[this.index[j]]){
j = j+1
}
if(this.data[this.index[k]] >= this.data[this.index[j]]){
break
}
[this.index[k],this.index[j]] = [this.index[j],this.index[k]]
this.reverse[this.index[k]] = k;
this.reverse[this.index[j]] = j;
k = j;
}
}
extractMax(){
if(this.count > 0){
let ret = this.data[this.index[1]]
//console.log(this.data[1]+"----------------------------"+this.data[this.count])
if([this.index[1],this.index[this.count]] = [this.index[this.count],this.index[1]]){
this.reverse[this.index[1]] = 1;
this.reverse[this.index[this.count]] = 0;
this.index = this.index.slice(0,this.count)
this.count--
}
this.shiftDown(1)
return ret;
}
}
extractMaxIndex(){
if(this.count > 0){
let ret = this.index[1]-1;
//console.log(this.data[1]+"----------------------------"+this.data[this.count])
if([this.index[1],this.index[this.count]] = [this.index[this.count],this.index[1]]){
this.reverse[this.index[1]] = 1;
this.reverse[this.index[this.count]] = 0;
this.index = this.index.slice(0,this.count)
this.count--
}
this.shiftDown(1)
return ret;
}
}
getItem(i) {
this.contain(i)
return this.data[i+1]
}
contain(i){
if(i+1 >=1 && i+1 <= this.data.length){
return this.reverse[i+1] !=0;
}
}
change(i,item) {
this.contain(i)
i += 1;
this.data[i] = item
for(let j = 1; j<= this.count;j++){
if(this.index[j] ===i){
this.shiftUp(j);
this.shiftDown(j)
return
}
}
}
change2(i,item) {
this.contain(i)
i += 1;
this.data[i] = item
let j = this.reverse[i]
this.shiftUp(j);
this.shiftDown(j)
}
}
function main() {
let maxheap = new ImdexMaxHeap();
for (let i = 0; i < 20;i++){
maxheap.insert(i,Math.floor(Math.random()*100));
}
console.log(maxheap.data+"---------"+maxheap.index+"---------"+maxheap.reverse);
maxheap.extractMax()
console.log(maxheap.data+"---------"+maxheap.index+"------------"+maxheap.reverse);
}
main()写回答
1回答
-
我不确定我是否正确理解了你的问题。但是对于我们设计的这个结构，用户在调用insert(i,e)前，是需要自行判断一下 contain(i)的，如果返回false，才可以调用insert(i,e)，否则的话，只能使用change(i,e)。当然，为了安全起见，我们在insert里做这样的一个assert更严谨：
assert( !contain(i) );
这样，如果用户没有进行contain判断的话，插入重复索引，会抛出错误，就好像数组越界一样，是用户使用不当。当然，在实际的生产环境中，错误处理应该抛出异常一类的。
感谢你的提醒，现在我将github上的insert代码增加了这个assert，最终是这个样子：
// 传入的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); }不过，我们也可以将接口设计成，如果insert的索引i是已经存在的话，就相应的调用change逻辑。如果我们要在IndexHeap中重载[]这个运算符的话，这是一个好的设计。换句话说，如果调用myIndexHeap[6] = 42，先查看6这个索引在我们的索引堆中是否存在，若存在，则修改其对应元素为42（调用change）；否则，将索引6的元素42插入我们的索引堆（调用insert）。
希望解决了你的问题：）
522017-02-24
相似问题