Priority Queue
コードについての説明
優先度付きキューと呼ばれる挿入, 削除からなるクエリに対して効率よく最大値を返すデータ構造の実装である.
以下では二分ヒープを用いて実装している. 詳しい実装については他のサイトを参照されたい.
ちなみに python には heapq というライブラリがあり, そっちを使ったほうが速く計算できる.
時間計算量: 挿入, 削除 $\O (\log n)$, 最大値の参照 $\O (1)$
コード
class PriorityQueue:
def __init__(self, max_size):
self.array = [0]*max_size
self.size = 0
def size(self):
return self.size
def empty(self):
return self.size == 0
def push(self, data):
self.array[self.size] = data
index = self.size
while index != 0 and self.array[index] > self.array[(index-1)//2]:
self.array[index], self.array[(index-1)//2] = self.array[(index-1)//2], self.array[index]
index = (index-1)//2
self.size += 1
def top(self):
return self.array[0]
def pop(self):
self.size -= 1
self.array[0], self.array[self.size] = self.array[self.size], self.array[0]
index = 0
while 2*index+1 < self.size:
if 2*index+2 < self.size:
if self.array[2*index+2] > self.array[index] and self.array[2*index+2] >= self.array[2*index+1]:
self.array[2*index+2], self.array[index] = self.array[index], self.array[2*index+2]
index = 2*index+2
elif self.array[2*index+1] > self.array[index] and self.array[2*index+1] >= self.array[2*index+2]:
self.array[2*index+1], self.array[index] = self.array[index], self.array[2*index+1]
index = 2*index+1
else:
break
else:
if self.array[2*index+1] > self.array[index]:
self.array[2*index+1], self.array[index] = self.array[index], self.array[2*index+1]
index = 2*index+1
else:
break
verify 用の問題
AOJ : Priority Queue 提出コード (heapq を用いていないため TLE にはなっているがすべてのクエリに正答している)