Pengjielee's blog

理解堆

堆是一个完全二叉树；
堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值；

完全二叉树：除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。

几个例子：

堆1：大顶堆
         10
        /  \
       9    8
      /\    /\
     6  5  7  4
    /
   3 

堆2：大顶堆
         10
        /  \
       8    9
      /\    /\
     7  3  5  6
    /
   4 

堆3：小顶堆
         3
        /  \
       4    6
      /\    /\
     5  8  9  10
    /
   7

堆的存储及操作

1、堆的存储

完全二叉树适合用数组来存储。

        7
      /   \
     5      6
    / \     / 
   4   2   1 

用数组来存储： 
arr = [, 7, 5, 6, 4, 2, 1]
idx = 0  1  2  3  4  5  6

- 数组下标为0的位置置空；
- 数组中下标为i的节点的左子节点，就是下标为i* 2的节点，右子节点就是下标为i*2+1的节点，父节点就是下标为i/2的节点。

2、往堆中插入元素

往堆中插入一个元素后，需要继续满足堆的两个特性。

3、从堆中删除元素

实现大顶堆

class MaxHeap {
  constructor() {
    // 使用数组来存储，索引为0的位置默认置为0，主要方便获取左右子节点
    // 当下标 i 为父节点，下标 i * 2 为左子节点，下标 i * 2 + 1为右子节点
    this.storage = [0];
  }

  // 传入一个数组构建堆
  build(arr) {
    if (!Array.isArray(arr)) {
      return false;
    }

    // 初始化
    this.storage = [0];

    //插入元素
    for (let i = 0; i < arr.length; i++) {
      this.insert(arr[i]);
    }

    return true;
  }

  insert(nValue) {
    //添加节点值
    this.storage.push(nValue);

    //当前节点下标
    let nIndex = this.storage.length - 1;
    //当前节点的父节点下标
    let nFatherIndex = Math.floor(nIndex / 2);

    // 从下往上完成堆化
    while (nFatherIndex > 0) {
      // 当前节点值大于其父节点，则交换（构建大顶堆）
      if (this.storage[nIndex] > this.storage[nFatherIndex]) {
        var temp = this.storage[nIndex];
        this.storage[nIndex] = this.storage[nFatherIndex];
        this.storage[nFatherIndex] = temp;
      }
      // 更新当前节点下标
      nIndex = nFatherIndex;
      // 更新父节点下标
      nFatherIndex = Math.floor(nIndex / 2);
    }
  }

  //删除堆顶元素
  delete() {
    const heapTop = this.storage[1];
    //用最后一个元素替换堆顶元素
    this.storage[1] = this.storage.pop();

    //堆化（自上而下完成堆化）
    this._heapify();

    //返回删除的元素
    return heapTop;
  }

  _heapify() {
    const arr = this.storage,
      len = arr.length;
    let i = 1; // 大顶堆的第一个节点的下标（父节点）
    while (true) {
      //假设最大位置为 第一个节点的下标
      let maxPos = i;
      // 如果拥有叶左节点，并且叶左节点较大，则更新maxPos为左节点下标
      if (i * 2 <= len && arr[i] < arr[i * 2]) {
        maxPos = i * 2;
      }
      // 如果拥有叶右节点，并且叶右节点较大，则更新maxPos为右节点下标
      if (i * 2 + 1 <= len && arr[maxPos] < arr[i * 2 + 1]) {
        maxPos = i * 2 + 1;
      }
      // 循环直到i节点为最大值
      if (maxPos === i) {
        break;
      } 
      // 交换位置, 父节点为父/左/右中最大的一个（i下标处存最大值的节点，大顶堆嘛）
      const temp = arr[i];
      arr[i] = arr[maxPos];
      arr[maxPos] = temp;

      // i为左/右节点，并尝试向下查找更大的值（更新i的值）
      i = maxPos; 
    }
  }
}

测试代码：

var heap = new MaxHeap();
console.log(heap.storage); //[0]

heap.insert(10);
console.log(heap.storage); //[0,10]
10

heap.insert(9);
console.log(heap.storage); //[0,10,9]
   10
  /
 9

heap.insert(11);
console.log(heap.storage); //[0,11,9,10]
  11
  /\ 
 9  10

heap.insert(8);
console.log(heap.storage); //[0,11,9,10,8]
  11
  /\ 
 9  10
 /
8

heap.insert(22);
console.log(heap.storage); //[0,22,11,10,8,9]
  22
  /\ 
 11  10
 / \
8  9

heap.delete(); //22
console.log(heap.storage); // [0, 11, 9, 10, 8]
  11
  /\ 
 9  10
 /
8

heap.delete(); //11
console.log(heap.storage); // [0, 10, 9, 8]
   10
  /  \
 9    8

小顶堆

class MinHeap {
  constructor() {
    // 使用数组来存储，索引为0的位置默认置为0，主要方便获取左右子节点
    // 当下标 i 为父节点，下标 i * 2 为左子节点，下标 i * 2 + 1为右子节点
    this.storage = [0];
  }

  // 传入一个数组构建堆
  build(arr) {
    if (!Array.isArray(arr)) {
      return false;
    }

    // 初始化
    this.storage = [0];

    //入堆
    for (let i = 0; i < arr.length; i++) {
      this.insert(arr[i]);
    }

    return true;
  }

  insert(nValue) {
    //添加节点值
    this.storage.push(nValue);

    //当前节点下标
    let nIndex = this.storage.length - 1;
    //当前节点的父节点下标
    let nFatherIndex = Math.floor(nIndex / 2);

    // 从下往上完成堆化
    while (nFatherIndex > 0) {
      // 当前节点值小于其父节点，则交换（构建小顶堆）
      if (this.storage[nIndex] < this.storage[nFatherIndex]) {
        var temp = this.storage[nIndex];
        this.storage[nIndex] = this.storage[nFatherIndex];
        this.storage[nFatherIndex] = temp;
      }
      // 更新当前节点下标
      nIndex = nFatherIndex;
      // 更新父节点下标
      nFatherIndex = Math.floor(nIndex / 2);
    }
  }

  //删除堆顶元素
  delete() {
    const heapTop = this.storage[1];
    //用最后一个元素替换堆顶元素
    this.storage[1] = this.storage.pop();

    //堆化（自上而下完成堆化）
    this._heapify();

    //返回删除的元素
    return heapTop;
  }

  _heapify() {
    const arr = this.storage,
      len = arr.length;
    let i = 1; //小顶堆的第一个节点的下标（父节点）
    while (true) {
      let minPos = i;
      // 如果拥有叶左节点，并且叶左节点小于较小，则更新minPos为左节点下标
      if (i * 2 <= len && arr[i] > arr[i * 2]) {
        minPos = i * 2;
      }
      // 如果拥有叶右节点，并且叶右节点小于较小，则更新minPos为右节点下标
      if (i * 2 + 1 <= len && arr[minPos] > arr[i * 2 + 1]) {
        minPos = i * 2 + 1;
      }
      //如果已经是最小了，则直接退出
      if (minPos === i) {
        break;
      }
      // 交换节点，下标i处存放最小值节点(父/左/右中最小的，小顶堆嘛)
      const temp = arr[i];
      arr[i] = arr[minPos];
      arr[minPos] = temp;
      
      // 更新i的值，向下继续寻找最小的
      i = minPos;
    }
  }
}

测试代码：

var heap = new MinHeap();
console.log(heap.storage); //[0]

heap.insert(10);
console.log(heap.storage); //[0, 10]
10

heap.insert(9);
console.log(heap.storage); //[0, 9, 10]
  9
 /
10

heap.insert(11);
console.log(heap.storage); //[0, 9, 10, 11]
  9
 / \
10  11

heap.insert(8);
console.log(heap.storage); //[0, 8, 9, 10, 11]
    8
   / \
  9   10
 /
11

heap.insert(22);
console.log(heap.storage); //[0, 8, 9, 11, 10, 22]
    8
   / \
  9   11
 / \
10  22

heap.delete(); //8
console.log(heap.storage); //[0, 9, 10, 11, 22]
   9
  /  \
 10  11
 /
22

heap.delete(); //9
console.log(heap.storage); //[0, 10, 22, 11]
  10
 /  \
22  11 

heap.delete(); //10
console.log(heap.storage); //[0, 11, 22]
  11
 / 
22