優先度付きキューのヒープ実装

優先度付きキューに対して、以下の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)

largest = l

else:

largest = i

largest = r

if largest != i:

self.maxHeapify(largest)

python なら、heapqと、queue.PriorityQueueが使える