[Hip]双優先級キューレベル3(プログラマ)

にじゅうゆうせんれつ

質問の概要

デュアル・ユーティリティ・プリアンブル・キューとは、次の演算が可能なデータ構造です.

명령어      수신 탑(높이)
I 숫자      큐에 주어진 숫자를 삽입합니다.
D 1         큐에서 최댓값을 삭제합니다.
D -1        큐에서 최솟값을 삭제합니다.

パラメータとして双優先段キューで実行する演算操作を指定すると、すべての演算を処理した後、キューが空の場合は[0,0]、そうでない場合は[최댓값, 최솟값]を返します.

イニシアチブ

お尻の特性をうまく利用すれば解決できる簡単な問題です.

問題を解く

import heapq
def solution(operations):
    heap = []
    
    for operation in operations:
        command, n = operation.split()
        
        if command == 'I':
            heapq.heappush(heap, int(n))
        elif command == 'D' and heap:
            if n == '1':
                heap.pop()
            else:
                heapq.heappop(heap)
    if heap:
        heap.sort()
        return [heap[-1], heap[0]]
    else:
        return [0,0]

振り返る

コードの最後に、[최댓값, 최솟값]の部分を返すために臀部を整列させる.hipは,優先順位格納値に応じてソートを行わなくても挿入時にソート状態にすることができると考えている.しかし、これは大きな失算です.
お尻は完全バイナリツリーで構成されています.

ここでは並びとは別の場所が見えます.上のMin Heapの数字が1つの配列にある場合は、次のようになります.

# 정렬된 배열
[10, 15, 30, 40, 40, 50, 100]

せめてお尻だけなら

# 최소 힙
[10, 15, 30, 40, 50, 100, 40]

Levelkに基づいてインデックスが作成され、サブノードが検索されます.ここからソート後の配列と最小後尻配列の違いが分かる.
Q.完全バイナリツリーの最小お尻が必ずしも揃わない理由は何ですか?
A.子ノードが親ノードより大きくない場合は、完全バイナリツリーとして問題ありません.
たとえば、上のHeap Data Structureの30、100、40です.子ノード100,40が親ノード30より大きい場合、挿入の順序は子ノードの順序とは無関係である.
Q.最小お尻から最小値を抽出した場合どうなりますか?
最小hipの最小値はルートノードです.つまり、ルートノードを削除すると、次のように並べ替えられます.

ノード

を削除

最後のノードをルートノード位置

に変換する.

親ノードと子ノードを比較し、ノード

に移動する

サブノードが存在しないか、サブノードが時間なしに

を終了する.
質問の[최댓값, 최솟값]を返すために、お尻の構造を探して、発生した疑問点に答えて、過程で大きな助けを得ました.😄