堆的基本操作|算法专题 | 前端进阶之旅

# 基本结构

堆的底层实际上是一棵完全二叉树。
可以用数组实现
每个的节点元素值不小于其子节点 - 最大堆
每个的节点元素值不大于其子节点 - 最小堆

# 堆的构建

大顶堆

从第一个非叶子节点开始依次对数组中的元素进行下沉操作

和孩子节点的最大值max比较
大于max — 不需要在下沉
小于max — 和max交换位置 - 继续和下一层孩子节点比较，直到队列末尾

    function ajustMaxHeap(array, index, length) {
      for (let i = 2 * index + 1; i < length; i = 2 * i + 1) {
        if (i + 1 < length && array[i + 1] > array[i]) {
          i++;
        }
        if (array[index] >= [array[i]]) {
          break;
        } else {
          [array[index], array[i]] = [array[i], array[index]];
          index = i;
        }
      }
    }

    function createMaxHeap(arr, length) {
      for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
        ajustMaxHeap(arr, i, length);
      }
      return arr;
    }

@前端进阶之旅: 代码已经复制到剪贴板

小顶堆

从第一个非叶子节点开始依次对数组中的元素进行下沉操作

和孩子节点的最小值min比较
小于min — 不需要在下沉
大于min — 和min交换位置（下沉） - 继续和下一层孩子节点比较，直到队列末尾

    function ajustMinHeap(array, index, length) {
      for (let i = 2 * index + 1; i < length; i = 2 * i + 1) {
        if (i + 1 < length && array[i + 1] < array[i]) {
          i++;
        }
        if (array[index] < [array[i]]) {
          break;
        } else {
          [array[index], array[i]] = [array[i], array[index]];
          index = i;
        }
      }
    }

    function createMinHeap(arr, length) {
      for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
        ajustMinHeap(arr, i, length);
      }
      return arr;
    }