デュアルプライオリティキュー(Python)

私の質問に答える

受信

要素
operationsの要素(i split)を受信し、heapppop()を使用してi split[1]をリストスタックとmax heapに挿入します.

このときmax heapは(-i split[1],i split[1])の形で入れられ、降順で入れられる.

D 1の場合
max heap[0]からheapppop()を減算し、この値もリストheapから減算します.

D 2の場合
heap[0]からheapppop()を減算し、max heapからも減算します.

import heapq
def solution(operations):
    answer = []
    heap = []
    max_heap = []
    .
    # operations의 요소(i_split)들을 받아온다.
    for i in operations:
        i_split = i.split(" ")
        if i_split[0] == "I":
            heapq.heappush(heap,int(i_split[1]))
            heapq.heappush(max_heap,[(int(i_split[1])*-1), int(i_split[1])])
        else:
            if len(heap) == 0:
                pass
            elif i_split[1] == '1':
                num = heapq.heappop(max_heap)[1]
                heap.remove(num)
            else:
                num = heapq.heappop(heap)
                max_heap.remove([(num*-1), num])
.
    if len(heap) == 0:
        answer = [0,0]
    else:
        answer = [max(heap), min(heap)]
.    
    return answer

他人の解答

heapqはheapの最大値をどのように削除しますか.nlargest()を使用すると便利に動作します.

heap = heapq.nlargest(len(heap), heap)[1:]
heapq.heapify(heap)