Priority queue

Priority queue和queue一樣也有兩種形式 : max priority queue和min priority queue這兩種形式，Priority queue有許多不同實作的方式，下面介紹如何使用max queue來實作max priority queue。

priority queue就像是在處理代辦事項一樣，在一堆資料集合S中，取出最重要/最不重要的資料，每一筆資料都有一個相關的值，表示其優先度，稱為key。一個priority queue可以使用以下操作。

• INSERT(S, x) : 將元素插入到集合S中。
• MAXIMUM(S) : 回傳S中具有最大key的元素。
• EXTRACT-MAX(S) : 回傳S中具有最大key的元素，並將該元素自S中移除。
• INCREASE-KEY(S, x, k) : 將x的key設為k，也就是改變某一筆資料的優先性，如果k比原先x的key還要小，則不進行任何動作。

max proprity queue紀錄集合S中各各元素之間的優先級，以作業系統的調度來說，每一個應用程式之間都具有優先級，應用程式之間對於資源的調度與使用都具有優先級，排程器呼叫EXTRACT-MAX從所有等待中的應用程式中，選出最高優先級的來執行，執行完便將該應用程式自queue中丟棄。

排程器可以呼叫INSERT把一個新的應用程式加入到queue中。

Priority queue他不是queue，因為她支援很多類似queue的操作，像是從陣列的最後面插入元素(insert)，或是將最前面的元素丟棄(pop)。但是和queue不同的是元素之間的順序是取決於優先級，而不是放進來順序，因此稱為Priority queue。

Heap-Maximum

HEAP-MAXIMUM(A)
return A[1]

回傳第一個節點的key

時間複雜度 :

Extract Maximum

HEAP-EXTRACT-MAX(A)
if A.heap-size < 1
    error "heap underflow"
max = A[1]
A[1] = A[A.heap-size]
A.heap-size = A.heap-size - 1
MAX-HEAPIFY(A, 1)
return max

Extract Maximum回傳最大元素，同時將max heap中最小的元素放到1號節點上(避免在執行A.heap-size - 1時最小元素遺失)，並且從1號節點呼叫MAX-HEAPIFY，因為將最小元素放在1號節點違反max heap的規則，因此需要呼叫MAX-HEAPIFY維持max heap。

時間複雜度 : ，除了MAX_HEAPIFY需要以外，其餘操作皆為常數時間

範例: HEAP-EXTRACT-MAX(A)

Heap-Increase-Key

HEAP-INCREASE-KEY(A, i, key)
if key < A[i]
    error "new key is smaller than current key"
A[i] = key
while i > 1 and A[PARENT(i)] < A[i]
    exchange A[i] with A[PARENT(i)]
    i = PARENT(i)

透過不斷交換父節點的值，來增加優先級，每個節點的值表示其優先級，如，則表示該節點的編號。

時間複雜度: ，原因為在更新優先級時，從節點到跟節點的路徑長為，每一次操作為常數時間，因此需要

Insert-Value

MAX-HEAP-INSERT(A, key)
A.heap-size = A.heap-size + 1
A[A.heap-size] = -∞
HEAP-INCREASE-KEY(A, A.heap-size, key)

將原先的priority heap增加一個位置，並傳入想要插入到priority heap的key值，再透過HEAP-INCREASE-KEY將插入的key移動到正確的位置上。

時間複雜度 :

範例: MAX-HEAP-INCERT(A, 6)

C++實作(手刻)

#include <iostream>
#include <algorithm>

using namespace std;
typedef struct arr
{
    int heap_size = 6;
    int array_size = 6;
    int arr[7] = {-1, 1, 3, 4, 5, 7, 8};
} Arr;
int parent(int);
int left_child(int);
int right_child(int);
void build_max_heap(Arr &A);
void max_heapify(Arr &, int);
int heap_maximum(Arr &);
int extract_maximum(Arr &);
void heap_increase_key(Arr &, int, int);
void max_heap_insert(Arr &, int);
void show_heap(Arr &);
int main(void)
{
    Arr A;
    build_max_heap(A);
    show_heap(A);
    cout << "heap_maximum(A) = " << heap_maximum(A) << '\n';
    cout << "extract_maximum(A) = " << extract_maximum(A) << '\n';
    cout << "extract_maximum(A) = " << extract_maximum(A) << '\n';
    max_heap_insert(A, 12);
    show_heap(A);
    heap_increase_key(A, 2, 15);
    show_heap(A);
}
int parent(int i)
{
    if (i == 0)
    {
        return 0;
    }
    return i / 2;
}

int left_child(int i)
{
    return 2 * i;
}

int right_child(int i)
{
    return (2 * i) + 1;
}

void build_max_heap(Arr &A)
{
    A.heap_size = A.array_size;
    for (int i = A.array_size / 2; i >= 1; i--)
    {
        max_heapify(A, i);
    }
}

void max_heapify(Arr &A, int i)
{
    int l = left_child(i);
    int r = right_child(i);
    int largest = 0;
    if ((l <= A.heap_size) && (A.arr[l] > A.arr[i]))
    {
        largest = l;
    }
    else
    {
        largest = i;
    }
    if ((r <= A.heap_size) && (A.arr[r] > A.arr[largest]))
    {
        largest = r;
    }
    if (largest != i)
    {
        swap(A.arr[i], A.arr[largest]);
        max_heapify(A, largest);
    }
}

int heap_maximum(Arr &A)
{
    return A.arr[1];
}

int extract_maximum(Arr &A)
{
    if (A.heap_size < 1)
    {
        cout << "heap underflow" << '\n';
        return -1;
    }
    int max = A.arr[1];
    A.arr[1] = A.arr[A.heap_size];
    A.heap_size = A.heap_size - 1;
    max_heapify(A, 1);
    return max;
}

void heap_increase_key(Arr &A, int i, int key)
{
    if (key < A.arr[i])
    {
        cout << "new key is smaller than current key" << '\n';
        return;
    }
    A.arr[i] = key;
    while (i > 1 && A.arr[parent(i)] < A.arr[i])
    {
        swap(A.arr[i], A.arr[parent(i)]);
        i = parent(i);
    }
}

void max_heap_insert(Arr &A, int key)
{
    A.heap_size = A.heap_size + 1;
    A.arr[A.heap_size] = -99999;
    heap_increase_key(A, A.heap_size, key);
}

void show_heap(Arr &A)
{
    for (int i = 1; i <= A.heap_size; i++)
    {
        cout << A.arr[i] << ' ';
    }
    cout << '\n';
}

C++(使用STL)

#include <iostream>
#include <algorithm>
#inlcude <queue>

using namespace std;
int main(void)
{
    priority_queue<int, vector<int>, greater<int>> pq_up;
    priority_queue<int, vector<int>, less<int>> pq_down;
    pq_up.push(1);
    pq_up.push(3);
    pq_up.push(5);
    pq_up.push(7);
    pq_up.push(8);
    pq_up.pop();
    cout << pq_up.top() << '\n';

    pq_down.push(1);
    pq_down.push(3);
    pq_down.push(5);
    pq_down.push(7);
    pq_down.push(8);
    pq_up.pop();
    cout << pq_down.top() << '\n';
}

參考資料:Introduction to algorithms 3rd