優先度付きキューのヒープ実装
優先度付きキューに対して、以下の2つの操作を行うプログラム
insert(k)
要素kを挿入する
extractMax()
最大のキーを削除し、値を返す
二分ヒープ
maxヒープ条件を満たす
maxヒープ条件→節点のキーがその親のキー以下
minヒープ条件→節点のキーがその親のキー以上
ヒープでの節点番号の求め方
code:python
# 親の接点番号
def parent(i):
return i // 2
# 左の子
def left(i):
return i * 2
# 右の子
def right(i):
return i * 2 + 1
code:python
class MaxHeap(list):
def __init__(self, n=0):
list.__init__(self)
self.N = n
# keyをlistに挿入する
def insert(self, key):
self.N += 1
# 下の2段階を踏む理由がまだ理解できていない。。。
# 無限小の値を通さず、heapIncreaseKey()内のwhileループに行ってはだめなのか。。
self.append(-float("inf"))
self.heapInceaseKey(self.N, key)
# キーの変更
def heapInceaseKey(self, i, key):
return
_i = parent(i)
i = _i
# 最大のキーを返す
def heapExtract(self):
if self.N < 1:
raise "underflow"
# 根がmaxヒープ条件を破る可能性があるので、maxHeapify
self.N -= 1
self.maxHeapify(1)
return maximum
# maxヒープ条件に基づいて、keyを降下させる
def maxHeapify(self, i):
l = left(i)
r = right(i)
if l <= self.N and selfl > selfi: largest = l
else:
largest = i
largest = r
if largest != i:
self.maxHeapify(largest)
python なら、heapqと、queue.PriorityQueueが使える