來複習一下資料結構 - Priority Queue

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 由兩個特性構成

  1. complete binary tree
  2. 上述的 heap 特性

以 binary heap 實作的時間複雜度如下表,要特別注意的是,若以一般建 tree 的方式來 建 binary heap,時間複雜度其實是 $O(nlogn)$,但若以 bottom-up 的方式 heapify, 則可以壓在 $O(n)$ 以內,大致上的概念如下,細節可以參考 這個這個

  1. 第 $h$ 層,最多需作 $2^h * 0$ 次 heapify
  2. 第 $h - 1$ 層,最多需作 $2^{h-1} * 1$ 次 heapify
  3. 第 $h - 2$ 層,最多需作 $2^{h-2} * 2$ 次 heapify
  4. 第 $h - i$ 層,最多需作 $2^{h-i} * i$ 次 heapify
  5. 第 $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$

A complete binary tree stored in an array

本來想找找 linux kernel 裡面使用到 heap 的部份出來看,翻了一下 cstheory.stackexchange.com 上有名的討論串,發現似乎只有 cgroup 有用到,而 且還是 reference kernel 2.6 的 source code,在 master branch 找了一下卻沒找到, 才發現原來在今年年初被拔掉了,不過 heap library 還在,可以參考 prio_heap.cprio_heap.h

References


Comments