PriorityQueueの確認

PriorityQueueをPythonで表してみる。
こんなんで大きい順に出せるのかと思った。

class PriorityQueue(object):
    def __init__(self):
        self.l = []

    def push(self, x):
        self.l.append(x)
        sz = len(self.l)
        i = sz - 1

        while i > 0:
            p = (i - 1) // 2
            if self.l[p] >= x:
                break
            self.l[i] = self.l[p]
            i = p
        self.l[i] = x

    def pop(self):
        sz = len(self.l)
        if sz == 0:
            return None

        res = self.l[0]
        x = self.l[-1]
        i = 0

        while (i * 2 + 1) < sz:
            a = i * 2 + 1
            b = i * 2 + 2

            if b < sz and self.l[b] > self.l[a]:
                a = b

            if self.l[a] <= x:
                break
            self.l[i] = self.l[a]
            i = a
        self.l[i] = x

        self.l = self.l[:-1]

        return res

In [91]: a = PriorityQueue()

In [92]: a.push(2)
In [92]: a.push(2)

In [93]: a.push(2)

In [94]: a.push(4)

In [95]: a.push(5)

In [96]: a.push(20)

In [97]: a.push(215)

In [98]: a.push(23)

In [99]: a.push(12)

In [100]: a.l
Out[100]: [215, 12, 23, 5, 4, 2, 20, 2]

In [101]: a.pop()
Out[101]: 215

In [102]: a.pop()
Out[102]: 23

In [103]: a.pop()
Out[103]: 20

In [104]: a.pop()
Out[104]: 12

In [105]: a.pop()
Out[105]: 5

In [106]: a.pop()
Out[106]: 4

In [107]: a.pop()
Out[107]: 2

In [108]: a.pop()
Out[108]: 2

In [109]: a.pop()