queue.py

#!/usr/bin/env python
# coding: utf-8

def _upheap(heap, x):
    heap += [x]
    l = len(heap) - 1                   # 挿入する要素のindex
    while (l-1)/2 >= 0:                 # 親がいる場合
        if heap[(l-1)/2] > heap[l]:
            heap[(l-1)/2], heap[l] = heap[l], heap[(l-1)/2]
        l = (l-1)/2
    return heap

def _downheap(heap, n):
    size = len(heap)
    while True:
        c = 2*n+1
        if c >= size: break
        if c + 1 < size:
            if heap[c] > heap[c+1]: c += 1
        if heap[n] <= heap[c]: break
        heap[n], heap[c] = heap[c], heap[n]
        n = c


class PQueue:
    def __init__(self, buff = []):
        self.buff = buff[:]             # 参照渡しなのでコピーを渡す
        for n in xrange(len(self.buff) / 2 - 1, -1, -1):
            _downheap(self.buff, n)

    # データの追加
    def push(self, data):
        self.buff.append(data)          # 追加
        _upheap(self.buff, len(self.buff) - 1) # ヒープ再構築

    # 最小値を取り出す
    def pop(self):
        if len(self.buff) == 0: raise IndexError
        value = self.buff[0]            # 最小値
        last = self.buff.pop()
        if len(self.buff) > 0:
            # ヒープ再構築
            self.buff[0] = last
            _downheap(self.buff, 0)
        return value

    # 最小値を取り出す
    def peek(self):
        return self.buff[0]

    def isEmpty(self):
        return len(self.buff) == 0

# 簡単なテスト
if __name__ == '__main__':
    import random
    a = PQueue()
    for x in xrange(10):
        n = random.randint(0, 100)
        a.push(n)
        print n, 'min data = ', a.peek()
    while not a.isEmpty():
        print a.pop(),
    print
    data = [random.randint(0, 100) for x in range(10)]
    print data
    a = PQueue(data)
    while not a.isEmpty():
        print a.pop(),
    print