zhengrenzhe's blog   About

优先队列

优先队列类似于普通队列,它也具有先进先出的特性,但同时它会让较高优先级的元素先出,且同优先级的元素仍保持先进先出的顺序。从实现上来说,它与普通队列则是两个东西了,优先队列通常使用二叉堆来实现,普通队列则通常使用链表或数组来实现,这里我们就来用二叉堆来实现一个优先队列。

二叉堆类似于二叉树,也是一个父节点连接两个子节点的结构,但不同的是二叉堆对于左右子节点的顺序没有要求,只要父节点的值大于(或小于)等于任何一个子节点即可。

二叉堆一般用数组实现,将根结点放在数组中索引为 $1$ 的位置,那么第 $n$ 个位置的子节点分别为 $2n$ 和 $2n+1$。例如如下二叉堆:

                12
              /    \
             5      11
            / \    /  \
           2   3  7    9

在数组中存储的顺序为 $[null, 12, 5, 11, 2, 3, 7, 9]$

接着我们来构造节点的数据结构

interface IPriorityQueueItemWrapper<T> {
    item: IPriorityQueueItem<T>; // 实际节点
    index: number;  // 节点入队时的次序
}

interface IPriorityQueueItem<T> {
    weight: number; // 节点的权重
    value: T; // 节点携带的数据
}

接口 IPriorityQueueItemWrapper 作为队列中元素实际的类型,是由接口 IPriorityQueueItem 构造而来,这是因为需要 IPriorityQueueItemWrapper 接口中的 index 属性来记录每个节点入队时的次序,以此来实现同优先级情况下先入队的先出,具体如何使用放在后面实现出出入队接口时再说明。

简单起见,我们的优先队列只包含入队与出队两个方法

class PriorityQueue<T> {
    private items: Array<IPriorityQueueItemWrapper<T>> = [null];

    // 一个自增的入队次序值
    private insertedIndex = 0;
    public get newIndex() {
        return this.insertedIndex++;
    }

    public get size() {
        return this.items.length - 1;
    }

    public get isEmpty() {
        return this.size === 0;
    }

    public enQueue(item: IPriorityQueueItem<T>): this {}

    public deQueue(): IPriorityQueueItem<T> {}
}

首先来说入队,我们直接将被插入元素添加到items数组的尾部,此时二叉堆的有序状态可能会被打破,所以需要对它进行上浮操作,也就是将它与它的父节点不断交换,直到某个父节点大于它,则上浮结束。

仍以上面的二叉堆为例,我们需要插入元素10,将它插入到数组尾部后二叉堆变为了:

                12
              /    \
             5      11
            / \    /  \
           2   3  7    9
                        \
                        10

接着对10进行上浮,只要10的父节点值小于10,就将它与10进行交换,交换的结果为

                12
              /    \
             5      11
            / \    /  \
           2   3  7    10
                        \
                         9

现在二叉堆又保持有序状态了,上浮完成,这一过程用代码实现很简单:

// 计算父节点的索引
function parent(childIndex: number) {
    return Math.floor(childIndex / 2);
}

function ALessToB<T>(
    a: IPriorityQueueItemWrapper<T>,
    b: IPriorityQueueItemWrapper<T>,
) {
    if (a.item.weight !== b.item.weight) return a.item.weight < b.item.weight;
    else return a.index > b.index;
}

class PriorityQueue<T> {
    ...

    public enQueue(item: IPriorityQueueItem<T>): this {
        const itemWrapper: IPriorityQueueItemWrapper<T> = {
            index: this.newIndex,
            item,
        };
        this.items.push(itemWrapper);
        this.swim();
        return this;
    }

    private swim() {
        let index = this.size;
        while (
            index > 1 &&
            ALessToB(this.items[parent(index)], this.items[index])
        ) {
            swap(this.items, index, parent(index));
            index = parent(index);
        }
    }

    ...
}

注意这里的 ALessToB 函数,我们通过它来比较某个节点是否应该被交换。在两个节点权重不同的情况下,自然是权重小的元素比较小,如果两个节点权重相同时,则要比较两者入队的次序,因为次序是一个自增的数字,所以次序越大的节点入队越晚,也就越小(虽然权重是一样的),通过这个机制可以保证在权重相同的情况下,先入队的元素一定是后入队的元素的父节点,也就确保了同优先级时一定是先入队的元素先出队。

出队稍微复杂一点,首先将根结点元素与二叉堆数组中最后一个元素进行交换,原本的根结点就可以直接移除作为出队的返回值,新的根结点打破了堆的有序状态,所以需要对其下沉,也就是不断的将节点与其子节点中较大的一个进行交换,直到其的子节点均小于该节点,则下沉结束。

                9
              /    \
             5      11
            / \    /  \
           2   3  7    10

以上面的堆为例,将 9 与 12 交换后,直接将 12 移出数组,就完成了出队,此时堆失去了有序状态,所以要对 9 进行下沉操作。首先找出两个子节点较大的那一个,如果待下沉元素小于这个子节点,就将两者交换,并不断重复这个过程。在第一轮交换过后,二叉堆变成了:

                11
              /    \
             5      9
            / \    /  \
           2   3  7    10

接着进行第二轮交换:

                11
              /    \
             5      10
            / \    /  \
           2   3  7    9

此时堆又回到了有序状态,下沉完成,接着我们来实现这一过程:

class PriorityQueue<T> {
    ...

    public deQueue(): IPriorityQueueItem<T> {
        if (this.isEmpty) return null;
        swap(this.items, 1, this.size);
        const data = this.items.pop().item;
        this.sink();
        return data;
    }

    private sink() {
        let curIndex = 1;
        const maxIndex = this.size;
        while (2 * curIndex <= maxIndex) {
            let childIndex = 2 * curIndex;
            if (
                childIndex < maxIndex &&
                ALessToB(this.items[childIndex], this.items[childIndex + 1])
            )
                childIndex++;
            if (ALessToB(this.items[childIndex], this.items[curIndex])) return;
            swap(this.items, curIndex, childIndex);
            curIndex = childIndex;
        }
    }

    ...
}

现在我们的优先队列就实现完成了,它实现了让高优先级的元素先出队,同时同优先级的元素仍保持先进先出的顺序。

const q = new PriorityQueue<string>();

q.enQueue({ weight: 1, value: "A" });
q.enQueue({ weight: 2, value: "B" });
q.enQueue({ weight: 3, value: "C" });
q.enQueue({ weight: 1, value: "D" });
q.enQueue({ weight: 2, value: "E" });
q.enQueue({ weight: 2, value: "F" });
q.enQueue({ weight: 4, value: "G" });

console.log(q.deQueue()); // { weight: 4, value: 'G' }
console.log(q.deQueue()); // { weight: 3, value: 'C' }
console.log(q.deQueue()); // { weight: 2, value: 'B' }
console.log(q.deQueue()); // { weight: 2, value: 'E' }
console.log(q.deQueue()); // { weight: 2, value: 'F' }
console.log(q.deQueue()); // { weight: 1, value: 'A' }
console.log(q.deQueue()); // { weight: 1, value: 'D' }

← 归并排序  Github 加V认证 →