お尻って何?

フルバイナリツリー(Complete Binary Tree)
最大値最小値演算では,バイナリhipの時間複雑度はO(1)である.

BSTとHIPの違い

BSTは左右の大小関係を保障し,バイナリヒップホップは上下の大小関係を保障する.

挿入方法

最後に

要素

を挿入する.

親ノードよりも

の方が大きい
親ノードまたはルートノードよりも小さくなるまで、

を繰り返します.
挿入時の時間的複雑度O(log(N))

削除方法

最上位のルートノード(スタックなど)のみを削除できます.
削除後、お尻のルールを守らなければなりません.

ノードと上部の要素を交換してください.

最背面の要素(既存ルートノード)

を削除

で変更されたノードとサブノードを比較します.二人の子供の中でもっと大きい子供に比べて、自分より大きいと位置が変わります.

親ノードが一番下の2つ以上のノードになるまで、

子ノード

を繰り返します.
既存の

ノードを返します.

削除時の時間複雑度O(log(N))

Pythonで実施

Pythonでは、少なくともhip heapqモジュールがあります.
ここで最大のお尻を実現

class BinaryMaxHeap:
    def __init__(self):
        # 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
        self.items = [None]

    def __len__(self):
        # len() 연산을 가능하게 하는 매직 메서드 덮어쓰기(Override).
        return len(self.items) - 1

    def _percolate_up(self):
        # percolate: 스며들다.
        cur = len(self)
        # left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
        parent = cur // 2

        while parent > 0:
            if self.items[cur] > self.items[parent]:
                self.items[cur], self.items[parent] = self.items[parent], self.items[cur]

            cur = parent
            parent = cur // 2
            
     def _percolate_down(self, cur):
        biggest = cur
        left = 2 * cur
        right = 2 * cur + 1

        if left <= len(self) and self.items[left] > self.items[biggest]:
            biggest = left

        if right <= len(self) and self.items[right] > self.items[biggest]:
            biggest = right

        if biggest != cur:
            self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur]
            self._percolate_down(biggest)

    def insert(self, k):
        self.items.append(k)
        self._percolate_up()

    def extract(self):
        if len(self) < 1:
            return None

        root = self.items[1]
        self.items[1] = self.items[-1]
        self.items.pop()
        self._percolate_down(1)

        return root