Priority Queues，again!!

在讀書時，只要有修過資料結構課程，一定都有接觸過Priority Queue的概念，priority queue的應用範圍很廣泛，也知道高效的Priority Queue一般都會以Heap來實作，但隨著遠離學生時代，每天在繁雜的軟體架構中求生存，不斷地把時間花在debug、了解現存介面的使用，有時不免讓人覺得有些疲憊(當然啦，有時開發某些模組還是頗有挑戰性，但我一般80%的時間的確都是勞力為主:P)。所以為了讓自己保持清醒，今晚就來複習一下Priority Queues的概念吧~

Priority Queues通常至少支援兩個操作：insert和delete_min。如果需要動態改變元素的priority，那麼還會再支援increase_priority, decrease_priority。甚至，有時會需要頻繁的合併多個Priority Queues，所以merge_priority_queue有時也是必要的，而高效的merge需要更複雜的heap，像是binomial heap或是Fibonacci heap。

讓我們先考慮基本操作：insert以及delete_min就好。如果只要支援這兩個操作，我們可以簡單地利用binary heap來完成。由於binary heap的結構通常非常精簡，可以array來實作，所以從任一元素找尋其parent與children都非常快速。以下是我用C語言的試作代碼。

注意：雖然我有針對使用的型別別作了一般化，但對於內建型別(如整數)可能會帶來些許性能損失。當然啦，如果用C++，就可以用 template specialization 把這個問題去除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166

#include <stdio.h>
#include <stdlib.h>
 
/* ADT for priority queue */
struct priority_q;
 
struct priority_q_ele_ops {
    int (*is_larger)(void *lhs, void *rhs);
    void (*assign)(void *lhs, void *rhs);
};
 
struct priority_q *create_priority_q(int max_nr, int ele_size, void *min_ele, struct priority_q_ele_ops *pqe_ops);
void destroy_priority_q(struct priority_q *q);
void priority_q_insert(struct priority_q *q, void *e);
void priority_q_del_min(struct priority_q *q, void *min_ele);
 
/* we use heap to imp priority queue */
 
struct priority_q {
    int capacity;
    int cur_nr;
    int ele_size;
    void *elements;
    struct priority_q_ele_ops *pqe_ops;
} ;
 
struct priority_q *create_priority_q(int max_nr, int ele_size, void *min_ele, struct priority_q_ele_ops *pqe_ops)
{
    struct priority_q *q = NULL;
 
    q = malloc(sizeof(struct priority_q));
    if (!q) {
        fprintf(stderr, "in %s: malloc heap failed.\n", __func__);
        goto malloc_heap_fail;
    }   
 
    q->capacity = max_nr;
    q->cur_nr = 0;
 
    q->ele_size = ele_size;
    q->elements = malloc(ele_size*(max_nr+1));
    if (!q->elements) {
        fprintf(stderr, "in %s: malloc elements failed.\n", __func__);
        goto malloc_ele_fail;
    }
 
    q->pqe_ops = pqe_ops;
 
    /* set elements[0] as min_ele's value for later efficient testing */
    q->pqe_ops->assign(q->elements, min_ele);
 
    return q;
 
malloc_ele_fail:
    free(q);
malloc_heap_fail:
    return NULL;
}
 
void destroy_priority_q(struct priority_q *q)
{
    free(q->elements);
    free(q);
}
 
static inline int pq_is_larger(struct priority_q *q, void *lhs, void *rhs)
{
    return q->pqe_ops->is_larger(lhs, rhs);
}
 
static inline void *pq_ith_ele(struct priority_q *q, int i)
{
    return (q->elements + (q->ele_size*i));
}
 
static inline void pq_assign(struct priority_q *q, void *lhs, void *rhs)
{
    q->pqe_ops->assign(lhs, rhs);
}
 
void priority_q_insert(struct priority_q *q, void *e)
{
    int i = 0;
 
    q->cur_nr += 1;
    for (i = q->cur_nr ; pq_is_larger(q, pq_ith_ele(q, i/2), e) ; i /= 2) {
        pq_assign(q, pq_ith_ele(q, i), pq_ith_ele(q, i/2));
    }
 
    pq_assign(q, pq_ith_ele(q, i), e);
}
 
void priority_q_del_min(struct priority_q *q, void *min_ele)
{
    int i = 0;
    int child = 0;
    void *last_ele = NULL;
 
    pq_assign(q, min_ele, pq_ith_ele(q, 1));
    last_ele = pq_ith_ele(q, q->cur_nr--);
 
    for (i = 1 ; (i*2) <= q->cur_nr; i = child) {
        child = i*2;
        if (child != q->cur_nr && pq_is_larger(q, pq_ith_ele(q, child), pq_ith_ele(q, child+1))) {
            child++;
        }
 
        if (pq_is_larger(q, last_ele, pq_ith_ele(q, child))) {
            pq_assign(q, pq_ith_ele(q, i), pq_ith_ele(q, child));
        } else {
 
            break;
        }
    }
 
    pq_assign(q, pq_ith_ele(q, i), last_ele);
}
 
/* test code, use int as element */
static int int_is_larger(void *lhs, void *rhs)
{
    int *L = lhs;
    int *R = rhs;
 
    return (*L) > (*R);
}
 
static void int_assign(void *lhs, void *rhs)
{
    int *L = lhs;
    int *R = rhs;
 
    *L = *R;
}
 
struct priority_q_ele_ops int_ops = {
    .is_larger = int_is_larger,
    .assign = int_assign
};
 
int main(void)
{
    int min = -99999;
    struct priority_q *q = NULL;
    int i = 0;
    int input[9] = {-9, -1, 10, 3, -7, 100, 75, 9, -3};
 
    q = create_priority_q(100, sizeof(int), &min, &int_ops);
    if (!q) {
        fprintf(stderr, "create q fail.\n");
    }
 
    for (i = 0; i < 9 ; ++i) {
        priority_q_insert(q, &input[i]);
    }
 
    for (i = 0; i < 9 ; ++i) {
        int val = 0;
        priority_q_del_min(q, &val);
        printf("%d ", val);
    }
 
    printf("\n");
 
    return 0;
}