JavaScript 实现一个 Heap (堆、完全二叉树、最小堆、最大堆)

heap.js

function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

/* 堆是完全二叉树 */
/* 使用数组来实现完全二叉树 */
class Heap {
  constructor(k) {
    this.data = [];
    this.capacity = k;
  }
  /* 返回堆的大小 */
  size() {
    return this.data.length;
  }
  /* 插入节点 */
  insert(node) {
    // 在数组的最末尾插入新节点
    let lastIdx = this.data.push(node) - 1;
    if (lastIdx >= 1) {
      // 自下而上调整子节点与父节点
      let parentIdx = this.getParentIdx(lastIdx);
      do {
        this.maxHeapify(parentIdx);
        parentIdx = this.getParentIdx(parentIdx);
      } while(parentIdx >= 0)
    }

    while (this.size() > this.capacity) {
      this.data.pop();
    }

    return this.data;
  }
  /* 计算父亲节点的下标 */
  getParentIdx(index) {
    return Math.floor((index - 1) / 2);
  }
  /* 计算左节点下标 */
  getLeftChildIdx(index) {
    return index * 2 + 1;
  }
  /* 计算右节点下标 */
  getRightChildIdx(index) {
    return index * 2 + 2;
  }
  /**
   * 保持以 index 为根节点的子树的最大堆。（单层）
   * @index 检查的起始下标
   * @returns 返回
   **/
  maxHeapify(index) {
    // 计算某节点与其左右子节点在位置上的关系
    const idx = index;
    let max = this.data[idx]; // 假设最大的节点是当前节点
    if (max === undefined) return;

    let maxIdx = idx;
    const leftIdx = this.getLeftChildIdx(idx);
    const left = this.data[leftIdx];
    const rightIdx = this.getRightChildIdx(idx);
    const right = this.data[rightIdx];

    if (left && left > max) {
      maxIdx = leftIdx;
    }

    if (right && right > max) {
      maxIdx = rightIdx;
    }

    if (maxIdx !== idx) {
      swap(this.data, maxIdx, idx);
    }
  }
  /* 堆排序 */
  sort() {

  }
}