Day-11 priority queue

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