JS优先队列

公众号：程序员波波

基于数据结构中堆可实现优先队列。

此处仅贴代码记录一下：

// 优先级大的排在前面
class PriorityQueue {
    // 构造函数，传入优先级比较函数
    constructor(cmp_func) {
        if (cmp_func) {
            this._cmp_func = cmp_func
        }
        else {
            this._cmp_func = (a, b) => {
                return a > b
            }
        }

        this._heap = []
        this._size = 0
    }

    //获取某个节点的父节点
    _parent(index) {
        let parent = Math.floor((index - 1) / 2);
        if (index > this._size - 1 || parent < 0) return null;
        return parent; //这里返回的 p 是在数组中的下标，数组是从0开始的
    }

    //获取某个节点的左孩子
    _leftChild(index) {
        let lt = 2 * index + 1;
        if (lt > this._size - 1) return null;
        return lt;
    }

    //获取某个节点的右孩子
    _rightChild(index) {
        let rt = 2 * index + 2;
        if (rt > this._size - 1) return null;
        return rt;
    }

    //元素下沉 对下标为i的元素向下进行调整，使堆保持其性质
    _downward(index) {
        let heap = this._heap;
        let lt = this._leftChild(index);
        let rt = this._rightChild(index);
        let larget = null;
        if (lt != null) { //左孩子为空则右孩子一定为空
            if (rt == null) {
                larget = lt;
            }
            else {
                larget = this._cmp_func(heap[lt], heap[rt]) ? lt : rt;
            }
            if (this._cmp_func(heap[index], heap[larget])) {
                return;
            }
            else {
                let tmp = heap[index];
                heap[index] = heap[larget];
                heap[larget] = tmp;
                this._downward(larget)
            }
        }
    }

    //元素上浮 对下标为i的元素进行向上调整，使堆保持其性质
    _upward(index) {
        let heap = this._heap;
        let parent = this._parent(index);
        while (index > 0 && this._cmp_func(heap[index], heap[parent])) {
            let tmp = heap[index];
            heap[index] = heap[parent];
            heap[parent] = tmp;
            index = parent;
            parent = this._parent(index);
        }
    }

    empty() {
        return this._size == 0;
    }

    size() {
        return this._size
    }

    push(item) {
        this._size += 1;
        if (this._heap.length >= this._size) {
            this._heap[this._size-1] = item;
        }
        else {
            this._heap.push(item)
        }
        this._upward(this._size-1);
    }

    top() {
        this._heap[0];
    }

    pop() {
        let top_item = this._heap[0];
        this._heap[0] = this._heap[this._size-1];
        this._size -= 1;
        this._downward(0);
        return top_item;
    }
}

export default PriorityQueue;