最大お尻(11279)

6759 ワード
白駿 優先キュー テキストリンク

Priority Queue


質問する


広く知られている資料構造の中に、最大お尻というものがあります.最大hipを使用して、次の演算をサポートするプログラムを作成します.
自然数xを配列に加える.
配列の最大値を出力し、配列から削除します.
プログラムは最初に空の配列から始まります.

入力


第1行は、演算の個数N(1≦N≦100000)を与える.次のN行には、演算に関する情報を表す整数xが与えられる.xが自然数の場合、xを配列に追加する演算です.xが0の場合、配列の最大値が出力され、配列から削除されます.入力した自然数は2^31未満です.

しゅつりょく


入力では、0は所定の回数に等しく、答えを出力します.配列が空で、最大値を出力する必要がある場合は、0を出力します.

1)Python優先度HIPモジュールを使用するかどうか不明な場合の回答
import sys

n = int(sys.stdin.readline())
li = []

for i in range(n):
    x = int(sys.stdin.readline())
    if x > 0:
        li.append(x)
    elif x == 0:
        if len(li) == 0:
            print(0)
        elif len(li) != 0:
            print(max(li))
            del li[max(li)]
2)heapqライブラリを知る際のプール
import sys
import heapq as hq

n = int(sys.stdin.readline())
heap = []

for i in range(n):
    x = int(sys.stdin.readline())
    if x:
        hq.heappush(heap, (-x, x)) # 최소 우선힙이면 hq.heappush(heap, x)
    else:
        if len(heap) >= 1:
            print(hq.heappop(heap)[1]) 
            # 최대 힙에서 가장 큰 값은 heap[1]이다. 즉 최대값의 인덱스가 1이다.
            # 최소 우선힙이면 heap[0]꼴로 최소값 조회
        else:
            print(0)
            
# 배열 => heap            
# heap = [4, 1, 7, 3, 8, 5]
# heapq.heapify(heap)
# print(heap) # [1, 3, 5, 4, 8, 7]
参照)
https://www.daleseo.com/python-heapq/
ツリーの作成
バックアップとリカバリ:dumpコマンドとrestoreコマンド