堆

二叉堆：完全二叉树
堆和数组：

注意：这里节点上的数字表示的是数组索引值，而不是节点保存的值
插入节点：

删除节点：

/*
 * @Author: LongSir
 * @LastEditTime: 2021-05-04 19:27:12
 * @description: 大根堆，节点元素最大
 */
class PriorityQueue {
    constructor(arr) {
        if (arr.length) {
            this.pq = [];
            this._buildTree(arr);
            return;
        }
        this.pq = [];
    }
    // 父亲节点
    parent(root) {
        return Math.floor((root + 1) / 2) - 1;
    }
    // 左孩子节点
    leftChild(root) {
        return root * 2 + 1;
    }
    // 右孩子节点
    rightChild(root) {
        return root * 2 + 2;
    }
    // 构建树
    _buildTree(arr) {
        Object.assign(this.pq, arr);
    }
    // 交互数组位置i和j
    _exch(i, j) {
        let temp = this.pq[i];
        this.pq[i] = this.pq[j];
        this.pq[j] = temp;
    }
    // pq[i]是否比pq[j]小
    _less(i, j) {
        if (this.pq[i] < this.pq[j]) {
            return -1;
        } else if (this.pq[i] === this.pq[j]) {
            return 0;
        } else {
            return 1;
        }
    }
    // 上浮
    _swim(k) {
        while (this._less(this.parent(k), k) < 0) {
            this._exch(this.parent(k), k);
            k = this.parent(k);
        }
    }
    // 下沉
    _sink(k) {
        while (this._less(k, this.leftChild(k)) < 0 || this._less(k, this.rightChild(k)) < 0) {
            if (this._less(this.leftChild(k), this.rightChild(k)) < 0) {
                this._exch(k, this.rightChild(k));
                k = this.rightChild(k);
            } else {
                this._exch(k, this.leftChild(k));
                k = this.leftChild(k);
            }
        }
    }
    show() {
        console.log(this.pq);
    }
    // 实现队列
    enqueue(val) {
        this.pq.push(val);
        this._swim(this.pq.length - 1);
    }
    dequeue() {
        let dqNode = this.pq.shift();
        let last = this.pq.pop();
        this.pq.unshift(last);
        this._sink(0);
        return dqNode;
    }
    // 取队首的值
    getFirst() {
        return this.pq[0];
    }
}

测试：

let arr = [10, 5, 6, 2, 3];
let priorityQueue = new PriorityQueue(arr);
priorityQueue.show();
priorityQueue.enqueue(7);
priorityQueue.dequeue(11);
priorityQueue.show();