大顶堆

一、认识

---

大顶堆是一个完全二叉树，每一个节点的值都大于或者等于其左右孩子节点的值为大顶堆；每一个节点的值都小于等于其左右孩子节点的值成为小顶堆；

堆满足完全二叉树 (n>0)性质 , 从上到下，从左到右对节点从 0 开始进行编号，对任意第 i 个节点:

• 父节点索引为 Math.floor((i-1)/2) 或者 (i - 1) >>> 1, 左子节点索引为 2i+1, 右子节索引点为 2i+2

• 大顶堆: array[i] >= array[2*i+1] && array[i] >= array[2*i+2]

• 小顶堆: array[i] <= array[2*i+1] && array[i] <= array[2*i+2]

二、思路

---

三、实现

---

class MaxHeap {
  constructor() {
    this.data = [];
  }

  compare(a, b) {
    return a - b;
  }

  /**
   * @description: 向大顶堆中添加元素
   * @param {*} value
   */
  push(value) {
    const index = this.data.length;
    this.data.push(value);
    this.shiftUp(this.data, index);
  }

  /**
   * @description: 构建大顶堆: 从数组中心元素直到起始元素, 依次调整当前节点到堆底
   * @param {*} data
   */
  build(data) {
    this.data = [...data];
    const halfLength = this.data.length >>> 1;
    for (let i = halfLength - 1; i >= 0; i--) {
      this.shiftDown(this.data, i, this.data.length);
    }
    return this.data;
  }

  /**
   * @description: 取出堆顶元素, 将末尾元素放到堆顶, 调整堆
   */  
  pop() {
    if (this.data.length === 0) {
      return null;
    }
    const first = this.data[0];
    const last = this.data.pop();
    if (first !== last) {
      this.data[0] = last;
      this.shiftDown(this.data, 0, this.data.length);
    }
    return first;
  }

  peek() {
    return this.data.length === 0 ? null : this.data[0];
  }

  /**
   * @description: 大顶堆排序  ---  从小到大
   */
  sort() {
    let data = [...this.data];
    // 1. 构建大顶堆: 从数组中心元素直到起始元素, 依次调整当前节点到堆底
    data = this.build(data);
    // 2. 交换末尾元素与堆顶元素, 调整堆顶元素至当前元素
    for (let i = data.length - 1; i > 0; i--) {
      [data[0], data[i]] = [data[i], data[0]];
      this.shiftDown(data, 0, i);
    }
    return data;
  }

  shiftUp(data, startIndex) {
    let i = startIndex;
    while (i > 0) {
      const parentIndex = (i - 1) >>> 1;
      const parent = data[parentIndex];

      if (this.compare(parent, data[i]) < 0) {
        [data[i], data[parentIndex]] = [data[parentIndex], data[i]];
        i = parentIndex;
      } else {
        return;
      }
    }
  }

  shiftDown(data, startIndex, endIndex) {
    let i = startIndex;
    const halfLength = endIndex >>> 1;

    while (i < halfLength) {
      const leftIndex = (i + 1) * 2 - 1;
      const left = data[leftIndex];
      const rightIndex = leftIndex + 1;
      const right = data[rightIndex];

      if (this.compare(left, data[i]) > 0) {
        if (rightIndex < endIndex && this.compare(right, left) > 0) {
          [data[i], data[rightIndex]] = [data[rightIndex], data[i]];
          i = rightIndex;
        } else {
          [data[i], data[leftIndex]] = [data[leftIndex], data[i]];
          i = leftIndex;
        }
      } else if (rightIndex < endIndex && this.compare(right, data[i]) > 0) {
        [data[i], data[rightIndex]] = [data[rightIndex], data[i]];
        i = rightIndex;
      } else {
        return;
      }
    }
  }
}

测试

const heap = new MaxHeap();
const array = [1, 3, 6, 10, 8, 12, 7, 4, 5, 9, 2];
array.forEach(item => {
  heap.push(item);
});
console.log('heap.data', heap.data);
array.forEach(() => {
  console.log(heap.pop());
});

heap.build([1, 3, 6, 10, 8, 12, 7, 4, 5, 9, 2]);
console.log(heap.data);
console.log(heap.sort());