priority queue
とある事情から
プログラミングコンテストチャレンジブックを読んでいる
p.73でC++の降順のPriorityQueueを利用している
pythonにはPriorityQueueは用意されてて
from Queue import PriorityQueue q = PriorityQueue()
とかすれば使えるのだがどうしても昇順にとる方法がわからなかったのでなんとなく作った↓
#!/usr/bin/env python class DescHeap: def __init__(self): self.heap = [] def push(self, val): i = len(self.heap) self.heap.append(val) while(i > 0): p = (i - 1) // 2 if(self.heap[p] >= val): break; self.heap[i] = self.heap[p] i = p self.heap[i] = val def pop(self): ret = self.heap[0] i = 0 x = self.heap.pop() size = len(self.heap) while(i * 2 + 1 < size): a = i * 2 + 1 b = i * 2 + 2 if(b < size and self.heap[b] > self.heap[a]): a = b if(self.heap[a] <= x): break; self.heap[i] = self.heap[a] i = a if(size != 0): self.heap[i] = x return ret def empty(self): if(len(self.heap) == 0): return True else: return False