优先级队列

• Back to Course Home

优先级队列是一种特殊的队列，其中每个元素都有一个优先级。优先级最高的元素是队头元素，优先级最低的元素是队尾元素。

基于线性表的优先级的队列

• 时间复杂度 \(O(N)\)

基于树的优先级队列

• 又称 二叉堆
• 时间复杂度：\(O(\log N)\)
• 分为：
  • 最大堆：根结点是最大元素
  • 最小堆：根结点是最小元素

• 实现：

  • 插入：新结点会先插入到完全二叉树最后一个结点，然后 向上过滤（percolate up）
  • 出队：移出根结点后，最后一个结点会填补根结点的位置，然后 向下过滤（percolate down）

  

#include <bits/stdc++.h>
using namespace std;

template <class T>
class PriorityQueue {
public:
    PriorityQueue();
    PriorityQueue(int capacity);
    PriorityQueue(const PriorityQueue<T>& pq);
    PriorityQueue(int capacity, T* x, int size);
    ~PriorityQueue();
    bool isEmpty();
    bool isFull();
    void print(int x = 1);
    void enQueue(T item);
    T deQueue();
    T getHead();
private:
    int currentSize;
    int capacity;
    T* items;
    void doubleCapacity();
    void percolateDown(int hole);
    void buildHeap();
};

template <class T>
PriorityQueue<T>::PriorityQueue() {
    capacity = 100;
    items = new T[capacity+1];
    currentSize = 0;
}

template <class T>
PriorityQueue<T>::PriorityQueue(int capacity) {
    capacity = capacity;
    items = new T[capacity+1];
    currentSize = 0;
}

template <class T>
PriorityQueue<T>::PriorityQueue(const PriorityQueue<T>& pq) {
    capacity = pq.capacity;
    items = new T[capacity+1];
    currentSize = pq.currentSize;
    for (int i = 0; i < currentSize; i++) {
        items[i] = pq.items[i];
    }
}

template <class T>
PriorityQueue<T>::PriorityQueue(int capacity, T* x, int size) {
    capacity = capacity;
    items = new T[capacity+1];
    currentSize = size;
    for (int i = 0; i < currentSize; i++) {
        items[i+1] = x[i];
    }
    buildHeap();
}

template <class T>
PriorityQueue<T>::~PriorityQueue() {
    delete[] items;
}

template <class T>
bool PriorityQueue<T>::isEmpty() {
    return currentSize == 0;
}

template <class T>
bool PriorityQueue<T>::isFull() {
    return currentSize == capacity;
}

template <class T>
void PriorityQueue<T>::print(int x) {
    for (int i = x; i <= currentSize; i++) {
        cout << items[i] << " ";
    }
    cout << endl;
}

template <class T>
void PriorityQueue<T>::enQueue(T item) {
    if (isFull()) {
        doubleCapacity();
    }
    int hole = ++currentSize;
    for (; hole > 1 && item < items[hole / 2]; hole /= 2) {
        items[hole] = items[hole / 2];
    }
    items[hole] = item;
}

template <class T>
T PriorityQueue<T>::deQueue() {
    T minItem = items[1];
    items[1] = items[currentSize--];
    percolateDown(1);
    return minItem;
}

template <class T>
T PriorityQueue<T>::getHead() {
    return items[1];
}

template <class T>
void PriorityQueue<T>::doubleCapacity() {
    T* oldItems = items;
    capacity *= 2;
    items = new T[capacity+1];
    for (int i = 0; i <= currentSize; i++) {
        items[i] = oldItems[i];
    }
    delete[] oldItems;
}

template <class T>
void PriorityQueue<T>::percolateDown(int hole) {
    int child;
    T tmp = items[hole];
    for (; hole * 2 <= currentSize; hole = child) {
        child = hole * 2;
        if (child != currentSize && items[child + 1] < items[child]) {
            child++;
        }
        if (items[child] < tmp) {
            items[hole] = items[child];
        } 
        else break;
    }
    items[hole] = tmp;
}

template <class T>
void PriorityQueue<T>::buildHeap() {
    for (int i = currentSize / 2; i > 0; i--) {
        percolateDown(i);
    }
}

优先级队列的应用

• 排队系统的模拟