数据结构-图-最小堆

最小堆

最小堆的实现是通过数组来模拟的，最小堆是一颗完全二叉树，主要通过上移操作、下移操作来实现。
代码实现
class MinHeap {
  constructor() {
    this.data = [];
    this.count = 0; // 下标从1开始，为了获取父节点的时候好计算
  }

  buildData(arr) {
    // data 第一个元素不存值，方便后续节点（表示为 i 2i 2i+1）依次表示第一个节点、第二个节点、第三个节点，以此类推
    for (let i = 0; i < arr.length; i++) {
      this.insert(arr[i]);
    }
  }

  swap(index1, index2) {
    const temp = this.data[index1];
    this.data[index1] = this.data[index2];
    this.data[index2] = temp;
  }

  getParentIndex(index) {
    return index >> 1;
  }

  getLeftChildIndex(index) {
    return 2 * index;
  }

  getRightChildIndex(index) {
    return 2 * index + 1;
  }

  insert(item, compare) {
    this.count++;
    this.data[this.count] = item;
    this.shiftUp(this.count, compare);
  }

  // 下移操作
  shiftDown(index, compare) {
    // 递归写法
    // const leftChildIndex = this.getLeftChildIndex(index);
    // const rightChildIndex = this.getRightChildIndex(index);
    // const minChildIndex = this.data[leftChildIndex] > this.data[rightChildIndex] ? rightChildIndex : leftChildIndex;
    // const conditionResult = compare
    //   ? compare(this.data[index], this.data[minChildIndex])
    //   : this.data[index] > this.data[minChildIndex];
    // if (conditionResult) {
    //   this.swap(index, minChildIndex);
    //   this.shiftDown(minChildIndex, compare);
    // }

    // 循环
    while (this.getRightChildIndex(index) <= this.count) {
      let leftChildIndex = this.getLeftChildIndex(index);
      let rightChildIndex = this.getRightChildIndex(index);
      const minChildIndex = this.data[leftChildIndex] > this.data[rightChildIndex] ? rightChildIndex : leftChildIndex;
      const conditionResult = compare
        ? compare(this.data[index], this.data[minChildIndex])
        : this.data[index] > this.data[minChildIndex];
      if (conditionResult) {
        this.swap(index, minChildIndex);
        index = minChildIndex;
      } else {
        break;
      }
    }
  }

  // 上移操作
  shiftUp(index, compare) {
    // 递归写法
    // if (index === 1) return;
    // const parentIndex = this.getParentIndex(index);
    // const conditionResult = compare
    //     ? compare(this.data[parentIndex], this.data[index])
    //     : this.data[parentIndex] > this.data[index];
    // if (conditionResult) {
    //   this.swap(parentIndex, index);
    //   this.shiftUp(parentIndex, compare);
    // }

    // 循环写法
    while (index >= 1) {
      const parentIndex = this.getParentIndex(index);
      const conditionResult = compare
        ? compare(this.data[parentIndex], this.data[index])
        : this.data[parentIndex] > this.data[index];
      if (conditionResult) {
        this.swap(parentIndex, index);
        index = parentIndex;
      } else {
        break;
      }
    }
  }

  size() {
    return this.count;
  }

  // 推出、取出堆顶元素
  extractMin() {
    const head = this.data[1];
    this.data[1] = this.data.pop();
    this.shiftDown(1);
    this.count--;
    return head;
  }

  // 堆是否为空
  isEmpty() {
    return this.count === 0;
  }

  // 获取最小堆中的堆中的元素
  getMin() {
    return this.data[1];
  }
}

module.exports = MinHeap;

// const mh = new MinHeap();
// mh.insert(9);
// mh.insert(6);
// mh.insert(2);
// mh.insert(1);
// mh.insert(4);
// console.log(mh.data);
// console.log(mh.getMin());
// console.log(mh.size());
// mh.buildData([9, 6, 2, 1, 4]);
// console.log(mh.data);
// mh.extractMin();
// console.log(mh.getMin());
// console.log(mh.size());
最小堆

CATALOG

FEATURED TAGS

FRIENDS
