大纲

  • 堆尾添加节点功能
  • 弹出堆顶节点功能
  • 自顶向下排序功能
  • 自下向顶排序功能
  • 元素大小比较函数

    预览

    ```javascript /**
    • 例如小顶堆堆:
    • 1
    • 3 5
    • 4 6 8 10
    • 数组化: [1, 3, 5, 4, 6, 8, 10];
    • */

/**

  • 取出堆顶[1]
  • ?
  • 3 5
  • 4 6 8 10
  • 数组化: [, 3, 5, 4, 6, 8, 10];
  • 将堆尾的节点放入堆顶,然后自顶向下排序
  • 10
  • 3 5
  • 4 6 8
  • 数组化: [10, 3, 5, 4, 6, 8]; */
    1. <a name="IK8Bw"></a>
    2. ### compare
    3. ```javascript
    4. function compare(a, b) {
    5.   return a - b;
    6. }

    siftDown(自顶向下排序)

    ```javascript /**
  • 将堆尾的节点放入堆顶,然后自顶向下排序
  • 10
  • 3 5
  • 4 6 8
  • 数组化: [10, 3, 5, 4, 6, 8]; *
  • 数组长度为6, 只要下个遍历的父节点 大于或者等于 数组的一半,就代表没有子节点,可以结束遍历
  • 左子节点: (当前父节点 + 1) * 2 - 1;
  • 假如父节点下标是0,左节点的位置就是 1, 3, 7, 15, 31, 63…
  • 可以发现的规律, 父节点的左子节点,一定是 父节点下标 * 2 + 1

  • leftIdnex = (x << 1) + 1

  • 父节点的右子节点就是左节点 + 1 *

  • 当每次比较完父节点跟子节点的大小时
  • 假如 下标0的元素是(10), 左子节点下标1的元素是(3),右子节点下标2的元素是(5)
  • 比较三个数,下标1的元素(3)最小,将它放入下标0的父节点,将下标0的父节点放入下标1
  • 3
  • 10 5
  • 4 6 8
  • 此时 下一个比较的父节点应该是下标1的元素10
  • 因为它的节点发生了变化,需要重新比较它的左右子节点 *
  • 比较完堆的最后一个父节点的时候,这个堆就已经最小化完成了 */

/**

  • @summary堆顶开始比较每个节点的左右子节点与父节点的大小
  • @param heap 堆
  • @param node 节点元素
  • @param i 当前父节点
  • @return {void} */ function siftDown(
    1.   heap,
    2.  node,
    i, ) {
    1.   let parentIndex = i;
    2.   let length = heap.length;
    3. let halfLength = length >>> 1;
    while(parentIndex < halfLength) {
    1.           const leftIndex = (parentIndex << 1) + 1;
    2.     const left = heap[leftIndex];
    3.           const rightIndex = leftIndex + 1;
    4.           const right = heap[rightIndex];
    5.     // 进入到这一步,一定是有左子节点的,因为parentIndex < 堆一半的长度才能进循环
    6.     if (compare(left, node) < 0) {
    7.                   if (rightIndex < length && compare(right, left) < 0) {
    8.                       heap[parentIndex] = right;
    9.         heap[rightIndex] = node;
    10.         parentIndex = rightIndex;
    11.                   } else {
    12.                       heap[parentIndex] = left;
    13.         heap[leftIndex] = node;
    14.         parentIndex = leftIndex;
    15.                   }
    16.           } else if (rightIndex < length && compare(right, node) < 0) {
    17.                   heap[parentIndex] = right;
    18.       heap[rightIndex] = node;
    19.         parentIndex = rightIndex;
    20.           } else {
    21.       return;
    22.   }
    23.   }
    } ```

    siftUp(自下向顶排序)

    ```javascript /**
  • 向堆尾添加一个节点,然后自下向顶排序
  • 2
  • 3 10
  • 4 6 8 1
  • 数组化: [2, 3, 10, 4, 6, 8, 1]; *
  • 先查找到当前添加的节点下标的父节点
  • 下标6的父节点下标是2,下标5的父节点下标是2,下标4的父节点下标是1,….
  • 6 -> 2, 5 -> 2, 4 -> 1, 3 -> 1, 2-> 0, 1 -> 0
  • 有上面的规律可得当前下标的父节点计算方式为 ((子节点 - 1) / 2)向下取整
  • parentIndex = (x - 1) >>> 1; *
  • 当每次比较完父节点跟子节点的大小时
  • 假如 当前堆尾添加了下标为6的元素(1),父节点下标2的元素(10)
  • 2
  • 3 10
  • 4 6 8 1
  • 比较两个元素,下标6比下标2的元素小,交换两个下标的元素,并且将下个比较的下标置为这个下标2
  • 2
  • 3 1
  • 4 6 8 10
  • 下标为2的元素(2),父节点下标0的元素(1),进行比较,得到
  • 1
  • 3 2
  • 4 6 8 10
  • 此时下标为0,表示整个堆都已经最小化完成,并且实例图也表现一致 */

/**

  • @summary堆顶开始比较每个节点的左右子节点与父节点的大小
  • @param heap 堆
  • @param node 节点元素
  • @param i 当前添加的节点下标
  • @return {void} */ function siftUp(
    1.   heap,
    2.  node,
    i, ) {
    1.   let index = i;
    while(index > 0) {
    1.   const parentIndex = (index - 1) >>> 1;
    2. const parent = heap[parentIndex];
    3. if (compare(parent, node) > 0) {
    4.     heap[parentIndex] = node;
    5.   heap[index] = parent;
    6.   index = parentIndex;
    7. } else {
    8.     return;
    9. }
    }
    }
    1. <a name="kg5k9"></a>
    2. ### push(堆尾添加节点)
    3. ```javascript
    4. function push(heap, node) {
    5. // 当前的堆长度,就是节点的下标
    6. const index = heap.length;
    7. // 推入堆尾
    8. heap.push(node);
    9. // 自下向顶排序
    10. siftUp(heap, node, index);
    11. }

    pop(堆顶弹出节点)

    1. function pop(heap) {
    2.   if (heap.length === 0) {
    3.         return null;
    4. }
    5. // 拿出堆顶的节点
    6. const first = heap[0];
    7. // 弹出堆尾的节点
    8. const last = heap.pop();
    9. // 如果两个元素不相等,这个堆至少两个元素
    10. if (first !== last) {
    11.   // 将堆尾元素放入堆顶
    12.     heap[0] = last;
    13.   // 自顶向下比较,最小堆化
    14.   siftDown(heap, last, 0);
    15. }
    16. return first;
    17. }