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