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