iT邦幫忙

2021 iThome 鐵人賽

DAY 11
0
自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列 第 11

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

時間複雜度 : https://chart.googleapis.com/chart?cht=tx&chl=O(1)

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。

時間複雜度 : https://chart.googleapis.com/chart?cht=tx&amp;chl=O(lgn),除了MAX_HEAPIFY需要https://chart.googleapis.com/chart?cht=tx&amp;chl=O(lgn)以外,其餘操作皆為常數時間

範例: 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)

透過不斷交換父節點的值,來增加優先級,每個節點的值表示其優先級,如https://chart.googleapis.com/chart?cht=tx&amp;chl=A%5Bi%5Dhttps://chart.googleapis.com/chart?cht=tx&amp;chl=i則表示該節點的編號。

時間複雜度: https://chart.googleapis.com/chart?cht=tx&amp;chl=O(lgn),原因為在更新優先級時,從節點到跟節點的路徑長為https://chart.googleapis.com/chart?cht=tx&amp;chl=O(lgn),每一次操作為常數時間,因此需要https://chart.googleapis.com/chart?cht=tx&amp;chl=O(lgn)

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移動到正確的位置上。

時間複雜度 : https://chart.googleapis.com/chart?cht=tx&amp;chl=O(lgn)

範例: 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


上一篇
Day-10 heap與heap sort
下一篇
Day-12 決策樹(decision tree)
系列文
從0開始啃Introduction of algorithms心得與記錄30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言