# Chap. 09 - Priority Queue

> 參考書目 : Fundamentals of Data Structures in C (2nd), Ellis H., Sartaj S., Susan A.-F.
>
> 其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)

## Content

* [Sec. 9.1 Single and double end priority queue](#Sec-91-Single-and-double-end-priority-queue)
* [1. Single-end priority queue](#1-Single-end-priority-queue)
* [1.1 Max priority queue](#11-Max-priority-queue)
* [1.2 Min priority queue](#12-Min-priority-queue)
* [1.3 Implement of single-end priority queue](#13-Implement-of-single-end-priority-queue)
* [2. Double-end priority queue](#2-Double-end-priority-queue)
* [2.1 Implement of double-end priority queue](#21-Implement-of-double-end-priority-queue)

## Sec. 9.1 Single and double end priority queue

優先權佇列(priority queue)是一種 queue 的變形，集合中的所有元素都包含一個對應的優先權(priority)並根據此優先權進行排列。可分為單向優先權佇列(single-end priority queue)與雙向優先權佇列(double-end priority queue)。單向優先權佇列常使用 4 種方式實作：

1. Array
2. Linked list
3. Heap
4. Binary tree

其中又以 binary heap 最常使用。

> 關於 heap 與 binary heap 的介紹請參閱 [Chap. 05 - Tree](https://hackmd.io/kpb3BthlTkm4ISQrhCIWWA#2-Maximum-heap)

### 1. Single-end priority queue

單向優先權佇列依據排列順序不同，又可再分為最小優先權與最大優先權，兩者都支援以下的運算：

* 取出(peak)一個最小 or 最大優先權的元素
* 插入(push)一個任意優先權的元素
* 刪除(pop)一個最小 or 最大優先權的元素

以 binary heap 的實作為例，上述的運算可以做到以下的時間複雜度

| Peak | Push | Pop |
| :-: | :-: | :-: |
| $O(1)$ | $O(\log n)$ | $O(\log n)$ |

:::info
後續的實作 code 中皆以下面兩個 max heap 與 min heap 舉例。另外，此處以陣列實作的 binary heap 都是以 0-index 系統為主。
:::

> The following code is saved in `PriorityQueue.c`.

/**
 * The following is an example of max priority queue which is the output of newMaxPrior
 *   82
 *  /  \
 * 49  44
 * The following is an example of min priority queue which is the output of newMinPrior
 *   5
 *  / \
 * 8  12
 * Both of them use 0-index
 */

element *newMaxPrior(){
    element *ptr;
    MALLOC(ptr, sizeof(element) * MAX_SIZE);
    
    ptr[0].priority = 82;
    ptr[1].priority = 49;
    ptr[2].priority = 44;
    
    return ptr;
}

element *newMinPrior(){
    element *ptr;
    MALLOC(ptr, sizeof(element) * MAX_SIZE);

    ptr[0].priority = 5;
    ptr[1].priority = 8;
    ptr[2].priority = 12;

    return ptr;
}

#### 1.1 Max priority queue

最大優先權佇列的三種運算實作如下：

> The following code is saved in `PriorityQueue.c`.

// operation for max priority queue
element getMaxPrior(element *pq){
    /** get element with max priority in max priority queue
     * Parameters
     * ------------
     * pq: a max priority queue
     */
    return pq[0];
}

void pushMaxPrior(element *pq, element item, int *n){
    if (*n >= MAX_SIZE){
        fprintf(stderr, "The queue us FULL.\n");
        exit(EXIT_FAILURE);
    }

    // bubble up
    int i = (*n)++; // index of new element
    int parent = (i - 1) / 2;
    while ((i != 0) && (pq[parent].priority < item.priority)){
        pq[i] = pq[parent];
        i = parent;
        parent = (i - 1) / 2;
    }

    pq[i] = item;
}

element popMaxPrior(element *pq, int *n){
    if ((*n) <= 0){
        fprintf(stderr, "The queue us EMPTY.");
        exit(EXIT_FAILURE);
    }

    // bubble down
    element res = pq[0];      // root
    element temp = pq[--(*n)]; // take last element and minor 1
    int parent = 0, child = 2 * parent + 1;
    while (child < *n){
        // check right node exist and compare two children
        if ((child + 1 < *n) && (pq[child].priority < pq[child+1].priority)){
            child++;
        }

        // if the parent is larger than the largest child, stop
        if (temp.priority > pq[child].priority){
            break;
        }

        // otherwise, move to next level
        pq[parent] = pq[child];
        parent = child;
        child = 2 * parent + 1;
    }

    pq[parent] = temp;
    return res;
}

#### 1.2 Min priority queue

最小優先權佇列的三種運算實作如下：

> The following code is saved in `PriorityQueue.c`.

// operation for min priority queue
element getMinPrior(element *pq){
    return pq[0];
}

void pushMinPrior(element *pq, element item, int *n){
    if (*n >= MAX_SIZE){
        fprintf(stderr, "The priority queue is FULL.\n");
        exit(EXIT_FAILURE);
    }

    // bubble up
    int i = (*n)++; // last index
    int parent = (i - 1) / 2;
    while (i != 0 && pq[parent].priority > item.priority){
        pq[i] = pq[parent];
        i = parent;
        parent = (i - 1) / 2;
    }
    pq[i] = item;
}

element popMinPrior(element *pq, int *n){
    if (*n <= 0){
        fprintf(stderr, "The priority queue is EMPTY.\n");
        exit(EXIT_FAILURE);
    }

    // bubble down
    element res = pq[0];
    element temp = pq[--(*n)];
    int parent = 0, child = 2 * parent - 1;
    while (child < *n){
        if ((child + 1 < *n) && pq[child].priority > pq[child+1].priority){
            child++;
        }

        if (pq[parent].priority > pq[child].priority){
            pq[parent] = pq[child];
            parent = child;
            child = 2 * parent + 1;
        }
        else {
            break;
        }

        pq[parent] = temp;
    }

    return res;
}

#### 1.3 Implement of single-end priority queue

> The following code is save in `PriorityQueue-implement.c`.

#include "PriorityQueueADT.h"
#include <stdio.h>
#include <stdlib.h>

int main(void){
    element *maxPQ = newMaxPrior();
    int maxPQLen = 3;

    element *minPQ = newMinPrior();
    int minPQLen = 3;

    element item1 = {16}, item2 = {72}, item3 = {31}, item4 = {64};  // push to maxPQ
    element item5 = {101}, item6 = {11}, item7 = {23}, item8 = {10}; // push to minPQ
    element maxPrior, minPrior;

    // max priority queue
    puts("before push: ");
    printPQ(maxPQ, maxPQLen); // [82, 46, 44]
    pushMaxPrior(maxPQ, item1, &maxPQLen);
    pushMaxPrior(maxPQ, item2, &maxPQLen);
    pushMaxPrior(maxPQ, item3, &maxPQLen);
    pushMaxPrior(maxPQ, item4, &maxPQLen);

    puts("After push: ");
    printPQ(maxPQ, maxPQLen); // [82, 72, 64, 16, 49, 31, 44]

    puts("After pop: ");
    printf("pop element: %d\n", popMaxPrior(maxPQ, &maxPQLen).priority); // 82
    printPQ(maxPQ, maxPQLen); // [72, 49, 64, 16, 44, 31]
    
    // min priority queue
    puts("before push: ");
    printPQ(minPQ, minPQLen); // [5, 8, 12]
    pushMinPrior(minPQ, item5, &minPQLen);
    pushMinPrior(minPQ, item6, &minPQLen);
    pushMinPrior(minPQ, item7, &minPQLen);
    pushMinPrior(minPQ, item8, &minPQLen);

    puts("After push: ");
    printPQ(minPQ, minPQLen); // [5, 8, 10, 101, 11, 23, 12]

    puts("After pop: ");
    printf("pop element: %d\n", popMinPrior(minPQ, &minPQLen).priority); // 5
    printPQ(minPQ, minPQLen); // [8, 11, 10, 101, 12, 23]

    free(maxPQ);
    free(minPQ); 
    return 0;
}

---

考慮將兩個優先佇列合併的運算，可以再延伸出 2 種資料結構包含此運算: (1) 左傾樹(leftist tree) 與 (2) 二項式堆積(binomial heap)，這種結構稱為合併式優先佇列。若再進一步擴充合併式優先佇列：

* 刪除任意給定位置的元素
* 減少任意給定位置的元素的優先權

可以再延伸兩種資料結構: (1) 費氏堆積(fibonucci heap) 與 (2) 成對堆積(pairings heap)

:::info
* 參考書目中有這四種延伸的資料結構，但此處暫時省略
* 優先權佇列的基本操作除了上述三種(取出、插入刪除)以外，有些還包括調整優先權的運算
:::

### 2. Double-end priority queue

雙向優先權佇列(**d**ouble-**e**nd **p**riority **q**ueue, depq)同樣是 queue 的變形，支援以下的運算：

1. 取出(peak)最小優先權的元素
2. 取出(peak)最大優先權的元素
3. 插入(push)任意優先權的元素
4. 刪除(pop)最小優先權的元素
5. 刪除(pop)最大優先權的元素

由上述幾種運算可知，雙向優先權佇列是一種合併最小與最大優先權佇列的資料結構，常使用 doubly linked list 實作。以 doubly linked list 所實作的雙向優先權佇列可以做到以下的時間複雜度

| peakMin() | peakMax() | push() | popMin() | popMax() |
| :-: | :-: | :-: | :-: | :-: |
| $O(1)$ | $O(1)$ | $O(n)$ | $O(1)$ | $O(1)$ |

:::info
後續以 doubly linked list 實作雙向優先權佇列，且每個 doubly linked list 都有一個標頭節點(header node)
:::

> The following code is saved in `DoubleEndPriorityQueue.c`.

// peak
nodePointer getMaxPrior(nodePointer pq){
    nodePointer firstNode = pq->next;

    if (!firstNode){
        fprintf(stderr, "The priority queue is EMPTY.\n");
        return NULL;    
    }
    return firstNode;
}

nodePointer getMinPrior(nodePointer pq){
    nodePointer firstNode = pq->next;
    if (!firstNode){
        fprintf(stderr, "The priority queue is EMPTY.\n");
        return NULL;
    }

    while (firstNode->next){
        firstNode = firstNode->next;
    }
    return firstNode;
}

// insert
void pushPrior(nodePointer pq, nodePointer node){
    nodePointer ptr = pq->next; // firstNode

    // if priority is NULL, node is the first node
    if (!ptr){
        pq->next = node;
        node->prev = pq;
        node->next = NULL;
        return; // if no return, the function will proceed
    }

    // traversal the while list to find correct position until
    //  (1) ptr is last or
    //  (2) ptr < node
    while (ptr->next){
        if (ptr->priority < node->priority){
            break;
        }
        ptr = ptr->next;
    }

    // if ptr is last and ptr > node
    if ((!ptr->next) && ptr->priority >= node->priority){
        node->next = ptr->next;
        node->prev = ptr;
        ptr->next = node;
        return; // if no return, the function will proceed
    }

    // ptr < node
    node->next = ptr;       // node link to next
    node->prev = ptr->prev; // node link to prev
    ptr->prev->next = node; // prev link to node
    ptr->prev = node;       // ptr link to node
}

// delete
nodePointer popMaxPrior(nodePointer pq){
    nodePointer ptr = pq->next;
    
    if (!ptr){
        fprintf(stderr, "The priority queue is EMPTY.\n");
        return NULL;
    }
    pq->next = ptr->next;     // pq link to second node

    // if second node is not NULL
    if (ptr->next){
        ptr->next->prev = pq; // second node link to pq
    }
    
    // split ptr
    ptr->next = NULL;
    ptr->prev = NULL;

    return ptr;
}

nodePointer popMinPrior(nodePointer pq){
    nodePointer ptr = pq->next;

    // null list
    if (!ptr){
        fprintf(stderr, "The priority queue is  EMPTY.\n");
        return NULL;
    }

    // traversal whole list to last node
    // after traversal, ptr is the last node and we have to remove it
    while (ptr->next){
        ptr = ptr->next;
    }
    ptr->prev->next = NULL; // the previous of last node link to NULL

    // split last node
    ptr->next = NULL;
    ptr->prev = NULL;
    return ptr;
}

#### 2.1 Implement of double-end priority queue

##### Create queue

> The following code is saved in `DoubleEndPriorityQueue.c`.

// basic
nodePointer createQueue(){
    // create header node
    nodePointer header;
    MALLOC(header, sizeof(struct node));
    header->next = NULL;
    header->prev = NULL;

    return header;
}

nodePointer createNode(int priority){
    nodePointer node;
    MALLOC(node, sizeof(struct node));
    node->next = NULL;
    node->prev = NULL;
    node->priority = priority;

    return node;
}

void printPQ(nodePointer pq){
    nodePointer ptr = pq->next;

    printf("Priority Queue = ");
    while (ptr){
        printf("%d ", ptr->priority);
        ptr = ptr->next;
    }
    puts("");
}

void freePQ(nodePointer pq){
    nodePointer ptr;

    while (pq){
        ptr = pq;
        pq = pq->next;
        free(ptr);
    }
}

##### Implement

> The following code is saved in `DoubleEndPriorityQueue-implement.c`.

#include <stdio.h>
#include <stdlib.h>
#include "DoubleEndPriorityQueueADT.h"

int main(){
    nodePointer header = createQueue();
    nodePointer a, b, c, d, e;
    a = createNode(82);
    b = createNode(24);
    c = createNode(30);
    d = createNode(16);

    puts("After push: ");
    pushPrior(header, a);
    pushPrior(header, b);
    pushPrior(header, c);
    pushPrior(header, d);
    printPQ(header); // [82, 30, 24, 16]

    puts("After pop: ");
    nodePointer maxPrior = getMaxPrior(header);
    nodePointer minPrior = getMinPrior(header);
    nodePointer popMax = popMaxPrior(header);
    nodePointer popMin = popMinPrior(header);
    printPQ(header); // [30, 24]

    printf("maxPrior = %d\n", maxPrior->priority); // 82
    printf("minPrior = %d\n", minPrior->priority); // 16
    printf("popMax = %d\n", popMax->priority);     // 82
    printf("popMin = %d\n", popMin->priority);     // 16

    free(popMax);
    free(popMin);
    freePQ(header);

    return 0;
}