Heap

お尻

バイナリツリー

ツリー

すべてのノードには2つのサブツリー

があります.

ノードごとに最大2つのサブノードしかないツリー

左側サブノード

右側サブノード

級iにおける最大ノード数は2^i個

である.

高さhのバイナリツリーが持つことができる最小ノード数は(h+1)個,最大ノード数は(2^(h+1)−1個である.

完全バイナリツリー

高さh、ノード数nのとき、飽和バイナリツリーのノード番号1からnまで空席のないバイナリツリー

お尻

データ構造

は、完全なバイナリツリーにおけるキー値が最大またはキー値が最小のノードを検索するために使用される.

最小HIPは常にルートディレクトリにあり、最大HIPは常にルートディレクトリ

にある.
優先順位キューは、

hipの鍵を優先順位として使用して実現することができる.

臀部は整然とした構造ではなく、親が子供以上の条件を満たすだけで、整然としていない.

の実行時間は基本的に木の高さと同じであるためlogNであり,頂点ごとにhipソートが必要であるため,Nを乗じてlogNとする.

最大ヒップ

鍵値が最も大きいノードを検索するための完全なバイナリツリー

(親ノードのキー値>子ノードのキー値)

本ノード:キー値が最大のノード

最小ヒップ

鍵の値が最も小さいノードを検索するための完全なバイナリツリー

(親ノードのキー値<子ノードのキー値)

本ノード:キー値が最小のノード

ヒップ演算

#삽입 
a = 10 

def heap_insert(heap,a) :
    #힙에 가장 마지막에 자료를 넣는다. 
    heap.append(a)
    #힙의 길이
    last = len(heap)
    #루트노드가 아니면 
    while last != 1  :
        #부모는 현재에서 2를 나눈 몫 
        parent = lats//2
        #부모가 자식보다 작으면 위치 변경 
        if heap[parent] < heap[last] :
            heap[parent],heap[last] = hepa[last],heap[parent]
            last = parent
        else :
            break 
#삭제 
def heap_delete(heap) :
    #힙의 루트를 초기화 
    heap[1] = None 
    #트리의 루트에 마지막 값을 넣음 
    heap[1] = heap.pop()
    
    #루트의 번호 
    i = 1
    #힙의 마지막이 아니면 
    while 2*i+1 <len(heap) :
        #자식들중에 더 큰 값을 기준으로 
        if heap[2*i]<heap[2*i+1] :
            tmp = 2 *i +1 
        else :
            tmp = 2*i 
		#부모보다 자식이 크면 위치 변경 
        if heap[i] > heap[tmp] :
            heap[i],heap[tmp] = heap[tmp],heap[i]
            i = tmp 

ヒップホップは最小のヒップホップにのみ関与する.
hipqを最大値に書く場合は、減算を行い、最小値を探します.そして最大値を見つければいいです.