Priority Queues (Cousera Data Structure week3)
CouseraのData Strucureコースのweek3の内容です。
www.coursera.org
前回のweek2の内容の記事はこちら
rikeiin.hatenablog.com
Priority Queues (優先度付きキュー)
Priority Queueは通常のキューに格納されている要素に優先度がついたデータ構造である。
C++ではpriority_queue、JavaではPriorityQueue、Pythonではheapqとして実装されている。
典型的な用途としてはジョブのスケジューリングなどがあげられる。
priority queueは以下の操作を持っている。
- Insert(p)：新しい要素を優先度pで挿入する
- ExtractMax()：優先度が最大の要素を取り出す
オプションで以下の操作を定義することもある
単純な実装
ソートされていない配列・リスト
- Insert(e)
- 要素eを末尾に追加する
- 実行時間はO(1)
- ExtractMax()
- 配列・リストを走査する
- 実行時間はO(n)
ソートされた配列
- ExtractMax()
- 最後の要素を取り出す
- 実行時間はO(1)
- Insert(e)
- 要素eの場所を探す(二分探索でO(log n))、右の要素を一つずつづらし(O(n))、挿入する(O(1))
- 実行時間：O(n)
ソートされたリスト
- ExtractMax()
- 最後の要素を取り出す
- 実行時間：O(1)
- Insert(e)
- 要素eの場所を探し(二分探索が使えないため、O(n))、挿入(O(1))
- 実行時間：O(n)
実行時間まとめ
Priority Queues: Binary Heaps(バイナリーヒープ)
Binary max-heapの定義は子より親のほうが値が大きい場合の二分木である。
以下がヒープである例
ヒープではない例
基本的なヒープに対する操作
GetMax
Insert
新しい要素を木の末端の葉にくっつける。
この操作において子より親の値が大きくなればならないという条件を満たしていな場合、以下のSiftUpという操作を条件が満たすまで行う。
SiftUp
シフトアップは子の大きい値と親の小さい値を入れ替えるという操作であり、木がヒープの条件を満たすまで繰り返す。
実行時間はO(木の高さ)である。
ExtractMax
木の根と葉を入れ替えることで行う。
上の木に対してExtractMaxを行うと以下のようになる。
当然これはヒープの条件を満たしていないため、以下のSiftDownという操作を行う。
SiftDown
SiftDownは親の小さい値と子の大きいを入れ替えてノードを下にずらす操作である。
上の図の例では12と29を入れ替える。このとき左右の子の大きいほうと入れ替えること。
この操作をヒープの条件を満たすまで繰り返す。
もちろん実行時間はO(木の大きさ)
ChangePriority
任意のノードを任意の値に変える。その後にヒープの条件を満たすようにSiftUpかSiftDownを繰り返す。
Remove
削除したいノードの値を∞にかえる。
その後、ヒープの条件を満たすようにSiftUpを繰り返す（最終的に∞が根に来る）。
その後はExtractMaxと同じ操作を行う。
実行時間はO(木の高さ)
ヒープ操作のまとめ
- GetMaxはO(1)だが他の操作はO(木の高さ)
- 木は出来る限り浅くしたい
どうやって木を浅くするか？
Complete binary tree の定義は最後の深さ以外のノードが全て埋まっており、最後の深さのノードは左から順に埋まっていることである。
Complete binary tree の例：
Complete binary tree ではない例：
n個のノードを持つcomplete binary treeの深さは最大で
complete binary treeのメリットととして以下のように配列で表現できる。
complete binary tree をキープしておくために
- 新しい要素をInsertするときは最後の深さで左から順に挿入する
- ExtractMaxするときはルートノードと最後の葉と入れ替える
Complete Binary Tree まとめ
- すべての操作がO(log n)で動作して高速である(GetMaxはO(1))
- 配列で保持しておけるのでメモリ空間の効率がよい
- 実装が簡単
Heap Sort
Heap Sortのやり方
- ヒープ構造を作る
- ExstraMax()を繰り返す
ヒープ構造の作り方
- 下から上に向かっていくようにヒープ構造を修正していく
- 最初は深さ1のサブツリーから修正していき、ルートまでたどり着いたときにすべてのサブツリーに対してヒープ構造が保たれている
- 参考URL：Heap Sort Visualization
- SiftDownをO(n)ノードに行うため計算量はO(nlog n)
- ノードが葉に近ければShifDownは高速に行える
ヒープソートまとめ
- PriorityQueueは主にInsertとExtractMaxという操作を持つ
- リストと配列による実装は片方の操作はとても高速(O(1))だがもう片方の操作はとても遅い(O(n))
- バイナリーヒープによる実装は両方の操作がO(log n)で行え、かつメモリスペース的にも効率がよい
記事が長くなってしまったのでDisjoint Setに関する内容は別記事にします。
追記：練習がてらにpythonでヒープソートを行うコードを書いてみました。
import numpy as np import random class HeapBuilder(object): def __init__(self, array_length): self._heap = np.random.permutation(np.arange(1,array_length+1)) self.size = len(self._heap) def _parent(self, i): return (i - 1) // 2 def _leftChild(self, i): return 2 * i + 1 def _rightChild(self, i): return 2 * i + 2 def _swap(self, i, j): temp = self._heap[i] self._heap[i] = self._heap[j] self._heap[j] = temp def _siftUp(self, i): while (i > 0) and (self._heap[self._parent(i)] < self._heap[i]): self._swap(i, self._parent(i)) i = self._parent(i) def _siftDown(self, i, size): maxindex = i l = self._leftChild(i) if (l < size) and (self._heap[l] > self._heap[maxindex]): maxindex = l r = self._rightChild(i) if (r < size) and (self._heap[r] > self._heap[maxindex]): maxindex = r if i != maxindex: self._swap(i, maxindex) self._siftDown(maxindex, size) def buildHeap(self): for i in reversed(range(0, self._parent(self.size))): self._siftDown(i, self.size) def heapSort(self): self.buildHeap() n = self.size for _ in range(self.size): self._swap(0, n - 1) n -= 1 self._siftDown(0, n) def showHeap(self): print (self._heap) if __name__ == '__main__': heap = HeapBuilder(1000) heap.showHeap() heap.heapSort() heap.showHeap()
