class PriorityQueue:
    N          # 完全二分木のノード数
    A          # キューの要素を保持する配列
    heapSize   # 実際にデータを保持しているヒープサイズ

    insert(x):
        A[heapSize++] ← x
        upHeap(heapSize-1)

    top():
        return A[0]

    extract():
        val ← A[0]
        A[0] ← A[heapSize-1]
        heapSize--
        downHeap(0)
        return val

    upHeap(i): # 挿入ベースの実装
        val ← A[i]

        while True:
            if  i ≤ 0: break
            if A[parent(i)] ≥ val: break
            A[i] ← A[parent(i)]
            i ← parent(i)
        
        A[i] ← val

    downHeap(i): # 挿入ベースの実装
        largest ← i
        val = A[i]

        while True:
            if left(i) < heapSize and right(i) < heapSize:
                if A[left(i)] > A[right(i)] ):
                    largest ← left(i)
                else:
                    largest ← right(i)
            else if left(i) < heapSize:
                largest ← left(i)
            else if right(i) < heapSize:
                largest ← right(i)
            else:
                largest ← NIL

            if largest = NIL : break
            if A[largest] ≤ val: break
      
            A[i] ← A[largest]
            i ← largest

        A[i] ← val