数据结构-带优化的最小索引堆

带优化的最小索引堆

上文实现的最小索引堆，存在以下问题： 1 extractMin 需要把索引数组 pop 出来，导致索引数组大小发生变化 2 没有实现 change 方法，用于改变索引对应的值，如果要实现的话，需要通过索引遍历的方式去找到数据数组在排序后在索引堆的位置

所以在这里加入了反向索引堆的概念，主要是为了方便 change 的使用，可以通过小标直接找到数组排序后在索引堆的正确位置

代码实现

class IndexReverseMinHeap {
  constructor(compare) {
    this.data = []; // 数据
    this.indexes = []; // 索引
    this.reverses = []; // 反向索引
    this.compare = compare; // 比较函数

    this.count = 0;
  }

  compareFn(i, j) {
    if (this.compare) {
      return this.compare(this.data[this.indexes[i]], this.data[this.indexes[j]]);
    }

    return this.data[this.indexes[i]] > this.data[this.indexes[j]];
  }

  shiftUp(k) {
    while (k > 1 && this.compareFn(k >> 1, k)) {
      this.swap(k >> 1, k);
      this.reverses[this.indexes[k >> 1]] = k >> 1;
      this.reverses[this.indexes[k]] = k;
      k = k >> 1;
    }
  }

  shiftDown(k) {
    while (2 * k <= this.count) {
      let j = 2 * k;
      if (j + 1 < this.compareFn(j, j + 1)) {
        j++;
      }
      if (!this.compareFn(k, j)) break;

      this.swap(k, j);
      this.reverses[this.indexes[k]] = k;
      this.reverses[this.indexes[j]] = j;
      k = j;
    }
  }

  insert(index, item) {
    index += 1;
    this.data[index] = item;
    this.indexes[this.count + 1] = index;
    this.reverses[index] = this.count + 1;
    this.count++;
    this.shiftUp(this.count);
  }

  swap(i, j) {
    [this.indexes[i], this.indexes[j]] = [this.indexes[j], this.indexes[i]];
  }

  size() {
    return this.count;
  }

  isEmpty() {
    return this.count === 0;
  }

  extractMin() {
    const ret = this.data[this.indexes[1]];
    this.swap(1, this.count);
    this.reverses[this.indexes[this.count]] = 0;
    this.reverses[this.indexes[1]] = 1;
    this.count--;
    this.shiftDown(1);
    return ret;
  }

  extractMinIndex() {
    const ret = this.indexes[1] - 1;
    this.swap(1, this.count);
    this.reverses[this.indexes[this.count]] = 0;
    this.reverses[this.indexes[1]] = 1;
    this.count--;
    this.shiftDown(1);
    return ret;
  }

  getMin() {
    return this.data[this.indexes[1]];
  }

  getMinIndex() {
    return this.indexes[1] - 1;
  }

  contain(index) {
    return this.reverses[index + 1] !== 0;
  }

  getItem(index) {
    return this.data[index + 1];
  }

  change(index, newItem) {
    index += 1;
    this.data[index] = newItem;

    this.shiftUp(this.reverses[index]);
    this.shiftDown(this.reverses[index]);
  }
}

// test
// const imh = new IndexMinHeap();
// console.log('====== init ======');
// imh.insert(0, 7);
// imh.insert(1, 2);
// imh.insert(2, 9);
// imh.insert(3, 1);
// imh.insert(4, 5);
// console.log(imh.data);
// console.log(imh.indexes);
// console.log(imh.reverses);
// console.log(imh.getMin());
// console.log(imh.getMinIndex());

// console.log('====== extract min ======');
// imh.extractMin();
// console.log(imh.data);
// console.log(imh.indexes);
// console.log(imh.reverses);
// console.log(imh.getMin());
// console.log(imh.getMinIndex());
// console.log(imh.contain(0));

// console.log('====== extract min ======');
// imh.extractMin();
// console.log(imh.data);
// console.log(imh.indexes);
// console.log(imh.reverses);
// console.log(imh.getMin());
// console.log(imh.getMinIndex());
// console.log(imh.contain(0));

// imh.insert(3, 6);

// console.log('====== extract min ======');
// imh.extractMin();
// console.log(imh.data);
// console.log(imh.indexes);
// console.log(imh.reverses);
// console.log(imh.getMin());
// console.log(imh.getMinIndex());
// console.log(imh.contain(0));

// console.log('====== extract min ======');
// imh.extractMin();
// console.log(imh.data);
// console.log(imh.indexes);
// console.log(imh.reverses);
// console.log(imh.getMin());
// console.log(imh.getMinIndex());
// console.log(imh.contain(0));

module.exports = IndexReverseMinHeap;

带优化的最小索引堆

CATALOG

FEATURED TAGS

FRIENDS