デュアルプライオリティキュー(HIP)-PYTHON

問題の説明
デュアル・ユーティリティ・プリアンブル・キューとは、次の演算が可能なデータ構造です.
めいれいじゅしんとう
I数値キューに指定した数値を挿入します.
D 1キューから最値を削除します.
D-1キューから最大値を削除します.
パラメータとして2つの優先順位キューで実行する演算操作を指定した場合、すべての演算を処理した後、キューが空の場合[0,0]空でない場合、「最値、最上昇値」を返すソルバを実装します.
せいげんじょうけん
operationsは、長さが1または1000000未満の文字列配列です.
operationsの要素は、キューが実行する演算を表します.
要素はコマンドデータ形式で与えられます.最大値/最大値を削除する操作で複数の最大値/最大値がある場合は、1つだけ削除します.
空のキューからデータを削除する必要がある場合は、この操作は無視されます.
I/O例
operations return
[I 16,D 1][0,0]
[I 7,I 5,I -5,D -1][7,5]
I/O例説明
16を挿入すると、最大値が削除されます.[0,0]を返します.空ですから.
7、5、および-5を挿入して、最大値を削除します.最大値7、最小値5を返します.
に答える
最大および最小の問題はsortを用いて解決できるが,以前の問題プールを通してheapqを用いた最大および最小ルックアップはsortよりも速いことが分かった.もっと熟知するために、sortではなくheapを使います.
アルゴリズム#アルゴリズム#
各値は、最大値

および最小値hipに格納される.

D numの場合、
-最大値を削除してminheap

を再割り当て

D-numの場合、
-最小値を削除すると、最大数の

が再割り当てされます.

長さが0の場合、0を答えに入れます.または最大最小スケール

import heapq

def changeHeap(heap) :
    res = []
    for h in heap :
        heapq.heappush(res, -h)
    return res

def solution(operations):
    answer = []
    min_heap = []
    max_heap = []
    
    for op in operations :
        cmd , num = op.split(' ')
        num = int(num)
        
        if cmd == 'I' :
            heapq.heappush(min_heap,num)
            heapq.heappush(max_heap,-num)
        else :
            try:
                if num == 1 :
                    heapq.heappop(max_heap)
                    min_heap = changeHeap(max_heap)
                else :
                    heapq.heappop(min_heap)
                    max_heap = changeHeap(min_heap)
            except:
                continue
    if len(max_heap) != 0:
        answer.append(-max_heap[0])
    else:
        answer.append(0)
        
    if len(min_heap) != 0:
        answer.append(min_heap[0])
    else:
        answer.append(0)
    
    return answer

しかし、他の人のコードを見ると、heapを使うより簡単なコードが見えます.

import heapq

def solution(operations):
    h = []

    for i in operations:
        a, b = i.split()
        if a == 'I':
            heapq.heappush(h, int(b))
        else:
            if len(h) > 0:
                if b == '1':
                    h.pop(h.index(heapq.nlargest(1, h)[0]))
                else:
                    heapq.heappop(h)

    if len(h) == 0:
        return [0, 0]
    else:
        return [heapq.nlargest(1, h)[0], h[0]]

従来のコードのように最小臀部と最大臀部を別々に設定する必要がないという利点がある.
このコードの核心はh.pop(h.index(heapq.nlargest(1,h)[0])である.
nlarget(n,heap)関数は、n個の最大値からなるリストを返します.つまり、最初のパラメータに見つけたい最大値の個数を入れればいいのです!これにより、最大値が簡単に見つかり、コードも短く、時間も短くなります.🤘