堆（二叉堆）

二叉堆是一種特殊的二叉樹，存在以下特性

1. 完全二叉樹，表示樹的每一層都存在左側和右側的子節(jié)點（除了最后一層的葉子節(jié)點）
2. 二叉堆不是最小堆就是最大堆蝙场。最小堆允許你快速查找到最小的值偷遗，最大堆允許你快速查找到最大的值，對于每一個節(jié)點都存在大于等于（大頂堆）和小于等于（小頂堆）每個它的子節(jié)點

盡管二叉堆是一個二叉樹但是不一定是二叉搜索樹

二叉堆的表示

二叉堆有兩種表達方式伟姐， 第一種是動態(tài)的表達式收苏，也就是指針的方式，第二種使用一個數(shù)組通過數(shù)組的索引進行檢索父節(jié)點愤兵、左右孩子節(jié)點鹿霸；
如果我們給定的位置idx節(jié)點，根據(jù)完全二叉樹的特性可得：

1. 它的左節(jié)點位置為2*index+1
2. 它的右節(jié)點位置為2*index+1
3. 它的父節(jié)點為 (int)（index - 1）/2

二叉堆的操作

• insert(value) 插入新值秆乳，成功返回true否則返回false
• extract() 移除堆頂元素（最大值或者是最小值）返回移除的值
• getTop() 返回堆頂元素
• pop() 彈出堆頂后重新建堆
• isEmpty 判空

用途

1. 快速查找最大值最小值
2. 優(yōu)先隊列
3. 堆排序

代碼實現(xiàn)

    class MaxHeap {
      constructor() {
        this.heap = [];
      }
      getLiftIdx(idx) {
        return 2 * idx + 1;
      }
      swap(arr, a, b) {
        [arr[a], arr[b]] = [arr[b], arr[a]];
      }
      getRightIdx(idx) {
        return 2 * idx + 2;
      }
    
      getParentIdx(idx) {
        if (idx == 0) return undefined;
        return (idx - 1) >> 1;
      }
    
      insert(val) {
        if (val === undefined) return false;
        this.heap.push(val);
        //上移操作
        this.shiftUp(this.heap.length - 1);
        return true;
      }
    
      shiftUp(idx) {
        let parentIdx = this.getParentIdx(idx);
        while (idx > 0 && this.heap[parentIdx] < this.heap[idx]) {
          this.swap(this.heap, idx, parentIdx);
          idx = parentIdx;
          parentIdx = this.getParentIdx(idx);
        }
      }
    
      shiftDown(idx) {
        let maxIdx = idx;
        const left = this.getLiftIdx(idx);
        const right = this.getRightIdx(idx);
        let size = this.heap.length;
        if (left < size && this.heap[maxIdx] < this.heap[left]) {
          maxIdx = left;
        }
        if (right < size && this.heap[maxIdx] < this.heap[right]) {
          maxIdx = right;
        }
    
        if (maxIdx !== idx) {
          this.swap(this.heap, maxIdx, idx);
          this.shiftDown(maxIdx);
        }
      }
    
      size() {
        return this.heap.length;
      }
    
      isEmpty() {
        return this.heap.size === 0;
      }
    
      getTop() {
        return this.heap[0];
      }
    
      getList() {
        return this.heap;
      }
    
      pop() {
        if (this.isEmpty()) {
          return undefined;
        }
        if (this.size() === 1) {
          return this.heap.shift();
        }
        const top = this.heap.shift();
        this.shiftDown(0);
        return top;
      }
    }