スキューヒープ
#Data_Structure #Meldable_Heap
Abstract
再帰版のスキューヒープ (Skew heap) を実装した. 可能なら非再帰版にそのうち直したい
Explanation
TODO そのうち書く.
Implementation
SkewHeap クラス内で, SkewNode クラスを定義している. 以下のインスタンス変数を持つ:
SkewNode.key: 格納されている要素.
SkewNode.left / SkewNode.right: 当該頂点の左/右の子.
SkewNode.n_elems: 当該頂点の子孫の数.
SkewHeap クラスでは, 現在の根の頂点 (SkewNodeクラス) を SkewHeap.root に格納している.
Skew Heapの構築
Input
比較可能なオブジェクトからなるイテラブル iterable (空でもよい)
Output
イテラブルの要素を格納したスキューヒープ SkewHeap(iterable)
Time complexity
イテラブルの長さを$ Nとすると,
イテラブルが空のとき$ O(1)time,
そうでないとき, Push操作を繰り返すことで, amortized$ O(N \log N)time.
Meld操作
Input
SkewHeap other
Output
併合してできるSkewHeap SkewHeap.meld(other)
Time complexity
現在のSkewHeapの要素数を$ N_1, other の要素数を$ N_2とし, $ N = N_1 + N_2とすると, amortized$ O(\log N)time.
Pop操作
Input
なし.
Output
SkewHeap内の最小要素 val
Time complexity
現在のSkewHeapの要素数を$ Nとすると, amortized$ O(\log N)time.
Push操作
Input
SkewHeapに新たに格納する要素 key
Output
なし.
Time complexity
現在のSkewHeapの要素数を$ Nとすると, amortized$ O(\log N)time.
Top操作
Input
なし.
Output
SkewHeap内の最小要素 val
Time complexity
$ O(1)time.
なお, オリジナルのSkew Heapにはないが, 以下の機能も実装している.
要素数の確認
Input
なし.
Output
SkewHeap内の要素数 len(SkewHeap)
Time complexity
$ O(1)time.
SkewHeap内の要素かどうかのチェック
Input
要素 x
Output
要素 x がSkew Heapに含まれているかのBool値 x in SkewHeap
Time complexity
現在のSkewHeapの要素数を$ Nとすると, 深さ優先探索により$ O(N)time.
SkewHeapの木構造の可視化
Input
なし.
Output
SkewHeapの現在の状態を表した文字列
print(SkewHeap) のようにすれば幅優先探索順で表示される (子が無いところは None を表示).
Time complexity
現在のSkewHeapの要素数を$ Nとすると, 幅優先探索により$ O(N)time.
抽象化した実装もできるらしいが, やってない.
code:python
from collections import deque
class SkewHeap:
class SkewNode:
def __init__(self, key):
self.key = key
self.left = None; self.right = None
self._update()
def _update(self):
self.n_elems = 1 if self.key is not None else 0
if self.left: self.n_elems += self.left.n_elems
if self.right: self.n_elems += self.right.n_elems
return self
def __repr__(self): return 'SkewNode({})'.format(self.key)
def __init__(self, iterable=None):
self.root = None
if iterable: self._heapify(iterable)
def __len__(self): return self.root.n_elems if self.root is not None else 0
def __contains__(self, x):
if self.root is None: return False
stack = self.root
while stack:
v = stack.pop()
if x == v.key: return True
if v.left: stack.append(v.left)
if v.right: stack.append(v.right)
return False
def __repr__(self):
if self.root is None: return 'SkewHeap([])'
elements = []
q = deque(self.root)
while q:
v = q.popleft()
if v is None: elements.append(v); continue
elements.append(v.key)
q.append(v.left); q.append(v.right)
return 'SkewHeap({})'.format(str(elements))
@classmethod
def _heap(cls, skewnode):
hp = cls(); hp.root = skewnode
return hp
@classmethod
def _singleton(cls, key):
return cls._heap(cls.SkewNode(key))
def _heapify(self, iterable):
for it in iterable: self.push(it)
def meld(self, other):
if other.root is None: return self.root
elif self.root is None: self.root = other.root; return other.root
if self.root.key > other.root.key:
self.root, other.root = other.root, self.root
self.root.left, self.root.right = other.meld(self._heap(self.root.right)), self.root.left
return self.root._update()
def push(self, key):
sg = self._singleton(key)
self.meld(sg)
def pop(self):
if not self: return None
val = self.root.key
if not self.root.left: self.root = self.root.right
elif not self.root.right: self.root = self.root.left
else:
left_heap, right_heap = self._heap(self.root.left), self._heap(self.root.right)
self.root = left_heap.meld(right_heap)
return val
def top(self): return self.root.key if self else None
Verification
Skew Heap Visualizationで挙動は確認した.
実行速度についてはテストできていない.
References
ovifrisch/Python-Data-Structures (GitHub)
併合可能優先度付きキューを Python3 で書いちゃおう！
マージ可能ヒープ(Skew-Heap)
D. P. Mehta and S. Sahni (Editors), "Handbook of Data Structures and Applications", Chapman and Hall/CRC, 2004.