[数据结构学习笔记9] 堆（Heaps）

在日常生活中，我们常常有很多想法要去实现，但是时间有限，所以要把想法分优先级，哪个是最重要的，先做它。堆（heaps）是这样一个数据结构，它让你容易（O(1)）的获取最高优先级的想法，并且提供了快速（O(log n)）插入，移除想法操作。

堆分为最大堆和最小堆，最大堆就是说root是最大值，最小堆是说root是最小值。这里我们讨论的时候，讨论最大堆。最小堆的表示和处理方式和最大堆相反。

最大堆是一个Complete 二叉树，并且每个节点值都要大于它的子节点。

常见堆操作

插入节点

1. 如果树为空，则新节点为root节点

2. 如果树不为空，则从左往右，一次添加新的节点

3. 比较新节点和其父节点的大小，如果新节点大于父节点，则新节点和父节点互换

4. 重复步骤3，直到父节点大于新节点

移除节点，一般堆移除节点，指的是移除root

1. 把root和最后的叶子节点互换

2. 比较新的root节点和其孩子节点，如果新root比孩子节点小，那么把新root和两个孩子节点中较大的互换；重复这个步骤，直到新root节点比它的孩子节点大

代码实现（javascript）

这里我们要用数组的方式去表示堆。

请看这样一个堆：

                        50

                       |      |
                     15     18

                   |      |    |     |

                 14   2    13    1

               |     |    |

               2   3    0

用数组表示成这样：

1. 下标为i的节点的父节点，计算公式 Math.floor((i-1)/2)。注意这里适用于非root节点；

2. 下标为i的节点的左子节点，计算公式 2i+1。注意这里计算不能越界；

3. 下标为i的节点的右子节点，计算公式 2i+2。同样这里也不能越界。

class Heap {
  constructor() {
      this.heap = [];
   }  

   insert(value) {
       this.heap.push(value);
       this.#bubbleUp(this.heap.length - 1);
   }

   extractMax() {
        if (this.heap.length === 0) {
              return null;
         }
        if (this.heap.length === 1) {
              return this.heap.pop();
         }    
        const max = this.heap[0];
        const end = this.heap.pop();
        this.heap[0] = end;
        this.#bubbleDown(0);
        return max;
   }

   #bubbleUp(index) {
        if (index === 0) {
            return;
        }
        const parentIndex = Math.floor((index - 1) / 2);
        if (this.heap[index] > this.heap(parentIndex)) {
             [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
             this.#bubbleUp(parentIndex);
        }
   }

   #bubbleDown(index) {
         const leftChildIndex = 2 * index + 1;
         const rightChildIndex = 2* index + 2;
         let largestIndex = index;
         if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] > this.heap[largestIndex]) {
                largestIndex = leftChildIndex;
          }
         if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] > this.heap[largestIndex]) {
                largestIndex = rightChildIndex;
          }
         if (largestIndex !== index) {
                [this.heap[index], this.heap[largestIndex]] = [this.heap[largestIndex], this.heap[index]];
                this.#bubbleDown(largestIndex);
          }
    }


    getMax() {
           return this.heap[0];
    }

    size() {
           return this.heap.length;
    }

    isEmpty() {
           return this.heap.length === 0;
     }
}

使用Heap

let myHeap = new Heap();
myHeap.insert(14);
myHeap.insert(18);
myHeap.insert(50);
myHeap.insert(1);
myHeap.insert(3);
myHeap.insert(15);
myHeap.insert(2);

myHeap.extractMax(); // 50

时间复杂度

堆常应用于堆排序，优先队列，迪杰斯特拉算法发现图最短路径等等。