普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out) 的行为特征。

概念

普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。

在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出的行为特征。

也就是说,队列的元素不再是根据先进先出的原则,而是根据元素的 priority 为原则,来进行出队。我们常常会把 priority 较小的放在队列的前面。比如有这么一个普通的队列 {4,2,1,0,5,3},在优先队列里这个队列就会变成 {0,1,2,3,4,5}.

可以发现,实际上我们就是针对队列的元素进行了一个升序的排序,所以说排序这个东西是贯穿到整个优先队列里的东西,但问题是——如何排序

实现

实现优先队列一般有两种方法,第一种方法会比较简单,但是低效;第二种会稍微有一点点复杂,但是高效。在实际情况下我们一般都会使用第二种方法。

首先第一种方法是采用数组来进行实现的。其核心思想就是,每次插入一个元素,就会将这个元素与数组内已有的元素进行比较,直到它找到了一个位置k,k-1位置的元素比他小,k+1元素的位置比他大。由于我们要对数组内的每一个元素都进行比较,所以在 enqueue 的时候,我们的时间复杂度就是 O(n)。

但是,在 dequeue 的时候,因为我们已经排好序了。所以,我们只需要队列最前的元素(队列的最前在数组的最后)。

第二种方法则需要采用一种叫二叉堆的数据结构。我们可以看到,因为我们需要将元素排序,我们的时间复杂度必须是O(n)。但是,采用二叉堆,我们可以不用将所有的元素都进行排序——我们维持一个“半序”的结构就以及能够实现优先队列的目标。

不了解二叉堆的,可以戳一下这里.

二叉堆

简单来 recap 一下,首先二叉堆分为两种:

  1. min-heap
    The value of each node >= the value of its parent. Root is minimum-value element.
  2. max-heap
    The value of each node <= the value of its parent. Root is maximum-value element.

这里,我们将采用 min heap 来作为我们构造优先队列的堆


min-heap:
min heap

max-heap:
max heap


把这样一个树形结构的东西压缩到数组里,我们就要知道如何寻找左子节点,右子节点,以及父节点:

假设 k 是某一个索引,那么

  • 左子 index: 2 * k + 1
  • 右子 index: 2 * k + 2
  • 父 index: k-1 / 2(如果k为0,那么要特殊处理这一部分,因为 index = 0 时没有父节点)

采用了这种数据结构,我们的 enqueue 操作的时间复杂度就可以变成 O(logN)。dequeue的操作因为需要维持顺序的原因,也变成了 O(logN)。

优先队列——数组版

头文件:

#pragma once
#include "datapoint.h"

class PQSortedArray {
public:

    PQSortedArray();
    ~PQSortedArray();

    void enqueue(DataPoint element);
    DataPoint dequeue();
    DataPoint peek() const;
    bool isEmpty() const;
    int size() const;

    void clear();
    void printDebugInfo();

private:
    DataPoint* elements; // array of elements
    int allocatedCapacity;  // number of slots allocated in array
    int numItems;           // number of slots used in array

    void validateInternalState();
    void expand();

    DISALLOW_COPYING_OF(PQSortedArray);
};

源文件:

const int INITIAL_CAPACITY = 10;

PQSortedArray::PQSortedArray() {
    numItems = 0;
    allocatedCapacity = INITIAL_CAPACITY;
    elements = new DataPoint[allocatedCapacity];
}

PQSortedArray::~PQSortedArray() {
    delete[] elements;
}

void PQSortedArray::enqueue(DataPoint elem) {
    if(allocatedCapacity == numItems){
        expand();
    }

    int index = 0;

    for(int i = 0; i < numItems - 1; i++){
        if(elem.priority <= elements[i].priority && elem.priority >= elements[i+1].priority){
            index = i + 1;
            break;
        }
    }

    if(!isEmpty() && elem.priority < elements[numItems - 1].priority){
        index = numItems;
    }

    for(int i = numItems; i > index; i--){
        elements[i] = elements[i-1];
    }
    elements[index] = elem;

    numItems++;

    validateInternalState();
}

int PQSortedArray::size() const {
    return numItems;
}

DataPoint PQSortedArray::peek() const {
    if (isEmpty()) {
        error("Cannot peek empty pqueue");
    }
    int lastOccupiedSlot = numItems - 1;
    return elements[lastOccupiedSlot];
}

DataPoint PQSortedArray::dequeue() {
    if (isEmpty()) {
        error("Cannot deqeuue empty pqueue");
    }
    int lastOccupiedSlot = numItems - 1;
    numItems--;
    return elements[lastOccupiedSlot];
}

bool PQSortedArray::isEmpty() const {
    return size() == 0;
}

void PQSortedArray::clear() {
    numItems = 0;
}

void PQSortedArray::printDebugInfo() {
    for (int i = 0; i < size(); i++) {
        cout << "[" << i << "] = " << elements[i] << endl;
    }
}

void PQSortedArray::validateInternalState(){
    if (size() == 0 || size() == 1){
        return;
    }

    if (size() > allocatedCapacity) error("Too many elements in not enough space!");

    DataPoint lastElem = elements[0];
    for (int i = 1; i < size(); i++){
        DataPoint cur = elements[i];
        if (cur.priority > lastElem.priority){
            error("Internal state of the array is out of order!");
        }
        lastElem = cur;
    }
}

void PQSortedArray::expand(){
    DataPoint* newElements = new DataPoint[allocatedCapacity * 2];
    for(int i = 0; i < numItems; ++i){
        newElements[i] = elements[i];
    }
    delete elements;
    elements = newElements;
    allocatedCapacity *= 2;
}

优先队列——二叉堆

头文件:

class PQHeap {
public:

    PQHeap();
    ~PQHeap();

    void enqueue(DataPoint element);
    DataPoint dequeue();
    DataPoint peek() const;
    bool isEmpty() const;
    int size() const;
    void clear();
    void printDebugInfo();

private:
    DataPoint* elements;
    int allocatedCapacity;
    int numItems;

    void expand();
    void validateInternalState();

    int getParentIndex(int curIndex);
    int getLeftChildIndex(int curIndex);
    int getRightChildIndex(int curIndex);

    DISALLOW_COPYING_OF(PQHeap);
};

源文件:

const int INITIAL_CAPACITY = 10;

PQHeap::PQHeap() {
    elements = new DataPoint[INITIAL_CAPACITY];
    allocatedCapacity = INITIAL_CAPACITY;
    numItems = 0;
}

PQHeap::~PQHeap() {
    delete [] elements;
}

void PQHeap::enqueue(DataPoint elem) {
    if(numItems == allocatedCapacity){
        expand();
    }

    elements[numItems] = elem;
    int parentIndex = getParentIndex(numItems);
    int previousIndex = numItems;

    while(parentIndex != -1){ //-1 means no parent index
        if(elem.priority >= elements[parentIndex].priority){
            break;
        }else{
            DataPoint tmp = elements[parentIndex];
            elements[parentIndex] = elements[previousIndex];
            elements[previousIndex] = tmp;
            previousIndex = parentIndex;
            parentIndex = getParentIndex(previousIndex);
        }
    }

    numItems++;
    validateInternalState();
}

DataPoint PQHeap::peek() const {
    if(isEmpty()){
        error("Queue is empty!");
    }

    return elements[0];
}

DataPoint PQHeap::dequeue() {
    if(isEmpty()){
        error("Queue is empty!");
    }

    DataPoint dp = elements[0];
    elements[0] = elements[numItems - 1];
    numItems--;

    int leftChildIndex = getLeftChildIndex(0);
    int rightChildIndex = getRightChildIndex(0);
    int previousIndex = 0;

    while(leftChildIndex < numItems){
        int priority = elements[previousIndex].priority;
        int leftPriority = elements[leftChildIndex].priority;

        if(rightChildIndex < numItems){
            int rightPriority = elements[rightChildIndex].priority;
            if(priority > leftPriority || priority > rightPriority){
                if(leftPriority < priority && leftPriority < rightPriority){
                    DataPoint tmp = elements[previousIndex];
                    elements[previousIndex] = elements[leftChildIndex];
                    elements[leftChildIndex] = tmp;
                    previousIndex = leftChildIndex;
                    rightChildIndex = getRightChildIndex(previousIndex);
                    leftChildIndex = getLeftChildIndex(previousIndex);
                }else{
                    DataPoint tmp = elements[previousIndex];
                    elements[previousIndex] = elements[rightChildIndex];
                    elements[rightChildIndex] = tmp;
                    previousIndex = rightChildIndex;
                    leftChildIndex = getLeftChildIndex(previousIndex);
                    rightChildIndex = getRightChildIndex(previousIndex);
                }
            }else{
                break;
            }
        }
        else{
            if(leftPriority < priority){
                DataPoint tmp = elements[previousIndex];
                elements[previousIndex] = elements[leftChildIndex];
                elements[leftChildIndex] = tmp;
            }
            break;
        }
    }

    validateInternalState();

    return dp;
}

bool PQHeap::isEmpty() const {
    return numItems == 0;
}

int PQHeap::size() const {
    return numItems;
}

void PQHeap::clear() {
    numItems = 0;
}

void PQHeap::printDebugInfo() {
    for (int i = 0; i < size(); i++) {
        cout << "[" << i << "] = " << elements[i] << endl;
    }
}

void PQHeap::validateInternalState(){
    if (size() == 0 || size() == 1){
        return;
    }

    if (size() > allocatedCapacity) error("Too many elements in not enough space!");

    for (int i = 1; i < size(); i++){
        DataPoint cur = elements[i];
        DataPoint parent = elements[getParentIndex(i)];

        if(getLeftChildIndex(i) < numItems){
            DataPoint leftChildren = elements[getLeftChildIndex(i)];

            if(getRightChildIndex(i) < numItems){
                DataPoint rightChildren = elements[getRightChildIndex(i)];
                if(cur.priority > leftChildren.priority || cur.priority > rightChildren.priority){
                    error("The queue is out of order!1");
                }
            }else{
                if(cur.priority > leftChildren.priority){
                    error("The queue is out of order!");
                }
            }
        }
        if(cur.priority < parent.priority){
            error("The queue is out of order!");
        }
    }
}

int PQHeap::getParentIndex(int curIndex){
    if(curIndex == 0) return -1;
    return (curIndex - 1)/2;
}

int PQHeap::getLeftChildIndex(int curIndex){
    return 2*curIndex + 1;
}

int PQHeap::getRightChildIndex(int curIndex){
    return 2*curIndex + 2;
}

void PQHeap::expand(){
    DataPoint* newElements = new DataPoint[allocatedCapacity * 2];
    for(int i = 0; i < numItems; ++i){
        newElements[i] = elements[i];
    }
    delete elements;
    elements = newElements;
    allocatedCapacity *= 2;
}

应用

优先队列被运用到了计算机的各个领域,比如面试经典题目 topK 问题,以及经典的压缩算法——哈夫曼压缩等等。