Priority queue 有別於一般的 queue，每一個 element 都額外帶有優先值，愈優先的 (一般來說是優先值愈低的) 放在愈前面。Priority queue 是一個 Abstract Data Type， 有許多不同的實作方法，以 array 或 linked list 實作的時間複雜度如下表，
| Insertion | Removal | Construction | |
|---|---|---|---|
| array or linked list | $O(n)$ | $O(1)$ | $O(n^2)$ |
Binary Search Tree
Priority queue 也可以用 binary search tree 來實作，前提是必須是一棵 self-balancing binary search tree，否則效果可能會很差，例如長成一棵 degenerate tree (每個 node 皆只有一個 child)，幾乎可以看作是一個 linked list。 以 self-balancing BST 實作的時間複雜度如下表，
| Insertion | Removal | Construction | |
|---|---|---|---|
| array or linked list | $O(n)$ | $O(1)$ | $O(n^2)$ |
| self-balancing BST | $O(logn)$ | $O(logn)$ | $O(nlogn)$ |
Heap
最常用來實作 priority queue 莫過於 heap，heap 是一種樹狀的資料結構，當每一個 parent nodes 都大於 child nodes 時，稱為 max heap，反之，則稱為 min heap。 Heap 中又以 binary heap 最常見，binary heap 由兩個特性構成
- complete binary tree
- 上述的 heap 特性
以 binary heap 實作的時間複雜度如下表，要特別注意的是，若以一般建 tree 的方式來 建 binary heap，時間複雜度其實是 $O(nlogn)$，但若以 bottom-up 的方式 heapify， 則可以壓在 $O(n)$ 以內，大致上的概念如下，細節可以參考 這個 和 這個
- 第 $h$ 層，最多需作 $2^h * 0$ 次 heapify
- 第 $h - 1$ 層，最多需作 $2^{h-1} * 1$ 次 heapify
- 第 $h - 2$ 層，最多需作 $2^{h-2} * 2$ 次 heapify
- 第 $h - i$ 層，最多需作 $2^{h-i} * i$ 次 heapify
- 第 $h - h$ 層，最多需作 $2^{h-h} * h$ 次 heapify
總共所需的 heapify 次數為 $\sum_{i=0}^{h} i2^{h-i} = \sum_{i=0}^{h} i\frac{2^h}{2^i} = 2^h\sum_{i=0}^{h} \frac{i}{2^i} \leq 2^h\sum_{i=0}^{\infty} \frac{i}{2^i} \leq 2^h * 2 = 2^{h+1} \in O(n)$
| Insertion | Removal | Construction | |
|---|---|---|---|
| array or linked list | $O(n)$ | $O(1)$ | $O(n^2)$ |
| self-balancing BST | $O(logn)$ | $O(logn)$ | $O(nlogn)$ |
| binary heap | $O(logn)$ | $O(logn)$ | $O(n)$ |
Heap 常以 array 的方式儲存，下圖是一個 complete binary tree 以 array 儲存的示 意，$ith$ node 的 children 和 parent 可以很容易的算出來
- children: $2i + 1, 2i + 2$
- parent: $\lfloor \frac{i - 1}{2} \rfloor$
本來想找找 linux kernel 裡面使用到 heap 的部份出來看，翻了一下 cstheory.stackexchange.com 上有名的討論串，發現似乎只有 cgroup 有用到，而 且還是 reference kernel 2.6 的 source code，在 master branch 找了一下卻沒找到， 才發現原來在今年年初被拔掉了，不過 heap library 還在，可以參考 prio_heap.c 和 prio_heap.h。
Comments