白駿解題-最低hip 1927回

📜 理解问题

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

💡 問題の再定義

最小hip設定後、最小値から順次出力します.

▼▼▼計画作成

最小臀部には次の条件があります.
1.親ノードは常に子ノードより小さい.
2.最後のレベル以外のすべてのレベルがノードを満たしている必要があります.
3.最後のレベルにノードがある場合は、一番左の順に埋めます.
hipを構成する配列が存在する場合、以下の値を満たす.
A[i]の左手はA[2*i+1]
A[i]右の子孫はA[2*i+2]
A[i]の両親はA[(i-1)/2]
hipに値を入れるinsert関数は、次のように実現されます.
1.hip配列で最後の要素に値を追加します.
2.親要素と比較した後、親要素が子要素より大きい場合は、位置を交換し、現在のidxを親idxに変更します.
3.上記の手順をidx 0に繰り返します.
4.親要素が現在の要素より小さい場合は、終了します.
値からお尻を減算するpop関数は、次のように実現されます.
1.一番前の要素を取り除き、一番後ろの要素で前の要素を置き換えます.
2.上の要素では左側のノードと比較し、左側のノードが小さい場合は左側のノードと置き換えます.
3.右側ノードが存在し、右側ノードが左側ノードより小さい場合は、右側ノードを置き換えます.
4.適切な位置に達するまで、上記の手順を繰り返します.

💻 計画の実行

import sys


class Heap:
    def __init__(self):
        self.min_heap = []

    def insert(self, key):
        self.min_heap.append(key)
        idx = len(self.min_heap) - 1
        while idx > 0 and self.min_heap[int((idx - 1) / 2)] > self.min_heap[idx]:
            tmp = self.min_heap[int((idx - 1) / 2)]
            self.min_heap[int((idx - 1) / 2)] = self.min_heap[idx]
            self.min_heap[idx] = tmp
            idx = int((idx - 1) / 2)

    def pop_heap(self):
        if len(self.min_heap) > 1:
            min_value = self.min_heap[0]
            self.min_heap[0] = self.min_heap.pop()
            here = 0
            length = len(self.min_heap)
            while True:
                left = here * 2 + 1
                right = here * 2 + 2
                if left >= length:
                    break

                next_idx = here
                # 부모와 왼쪽 자식과 비교하고 왼쪽 자식이 더 작다면 넣기
                if self.min_heap[here] > self.min_heap[left]:
                    next_idx = left
                # 만약 오른쪽 자식이 있다면 왼쪽 자식과 비교후에 오른쪽 자식이 더 작다면 바꾸기
                if right < length and self.min_heap[next_idx] > self.min_heap[right]:
                    next_idx = right

                if next_idx == here:
                    break

                tmp = self.min_heap[next_idx]
                self.min_heap[next_idx] = self.min_heap[here]
                self.min_heap[here] = tmp

                here = next_idx
            return min_value
        else:
            return self.min_heap.pop()


if __name__ == '__main__':
    heap = Heap()
    N = int(sys.stdin.readline())
    result = []
    for _ in range(N):
        cmd = int(sys.stdin.readline())
        if cmd != 0:
            heap.insert(cmd)
        else:
            if len(heap.min_heap) > 0:
                result.append(heap.pop_heap())
            else:
                result.append(0)

    print(*result, sep='\n')

🤔 振り返る

Pythonのモジュールheapqを使用すると簡単に問題を解決できますが、学習のために直接実現します.