データ構造/アルゴリズムHip(Heap)とツリー

概要

ヒップホップ

hipはバイナリツリーの一種であり、루트노드は常に最大値または最高値を有する完全なバイナリツリーである.

木。

では、この陳樹は何でしょうか.まず、ツリーは次のように定義できます.
ツリー:
図から、頂点と幹線を用いてデートのレイアウト形式を抽象化し、データの対象は線形式を採用していることがわかる.
これは木が逆さまの形をしているため、木と呼ばれ、根元の1つのルートノード(Root Node)からハエ部分(Leaf Node)に発展した形です.ツリーには次の要素があります.

本ノード:ツリー構造のルートノード

リーフノード:最下部の最深ノード

親ノードと子ノード:ホストに接続された2つのノードがある場合、ルートノードに近いノードを親ノード、リーフノードに近いノードを子ノードと呼びます.上記の例では、「AはBおよびCノードの親ノードである」としている.ルートノードを除いて、すべてのノードには親ノードが1つしかありません.

高さ(または深さ*Depth*Depth、しきい値*Level):ツリーがいくつかのレベルの構造からなる要素を表し、ルートノードを0とし、サブノードに直線で接続するたびに1の値が追加されます.上記の例のツリーの高さは3です.

サブツリー:ツリーの構造を表示します.ツリーにツリーがある構造を確認できます.上記の例のツリーでは、Aをルートノードとするツリーのうち、Bをルートノードとするツリー、Cをルートノードとするツリー、Eをルートノードとするツリーが見られる.これらのメインツリーの他のツリーを「サブツリー」と呼びます.

シーケンス数:サブノードの数を表します.上記の例のツリーでは、ルートノードAの次元数は2である.BとCの2つのサブノードがあるからです.

バイナリツリー

hipはバイナリツリーの一種です.木を見てみましたが、このJinの木はどんなものですか?この松の木の意味は모든 노드의 차수(Degree)가 2 이하인 트리です.上のツリーの例を表示します.すべてのノードに2つのサブノードがあります.(つまりすべてのノードの回数が2未満)
さらにhipの概念に戻ると、hipはバイナリツリーの中でも「完全バイナリツリー」である.バイナリツリーの「度数」(Degree)構成のタイプを見てみましょう.

ほうわバイナリ

飽和ツリーは모든 높이에서 노드들이 다 채워져있는 이진트리を表す.すなわち,高さhのバイナリツリーを飽和バイナリツリーにするには,高さh−1のノードまで2次元を持たなければならない.

完全バイナリツリー

飽和バイナリツリーよりも条件が厳しい.高さがhである場合、h−2の高さノードには2つのサブノードのh−1が必要であり、これは飽和バイナリツリーの条件を満たし、高さhのノードは左側からバイナリツリーを充填することを示す.

ヒップホップ詳細

例

臀部を理解するために,すべての概念について説明した.臀部は以下の条件を満たす.

リーフノード(Leaf Node)を除いて、すべてのノードは2の次元数を持つ必要があります.

リーフノードは、左側から塗りつぶされる必要があります(=完全ツリー).

本のノードの値は、常に2つのサブノード(最大hop)/(最小hop)より大きいか小さい必要があります.

では、お尻はいったいどんな様子なのでしょうか.
図のツリーは、「完全バイナリツリー」の構造に従います.また、すべての親ノードの値は、2つの子ノードの値よりも大きくなります.値が20のルートノードの2つのサブノードの値は、それぞれ20の15および13未満である.

Pythonコードでヒップホップを実現

ヒップホップをリストで実現

PythonのBuilt-in資料構造listを利用すれば,これを容易に実現できる.hipは「完全バイナリツリー」の構造に従うため、ルートノードから各ノードにインデックス番号を追加できます.また、子ノードと親ノードのインデックス値を簡単に見つけることができます.次の例を参照してください.
hipを配列形式で実装する場合は、0番インデックスを空にする必要があります.これは、0番のインデックスからノードのインデックス値を計算して、ノードの子ノード/親ノードを検索できないためです.

ヒップホップ資料の構造方法

一般的に、hipは2つの方法を提供します.
1)追加値insert(item):追加値がhip構造を破壊しないことを確認する
2)減算remove():「ルートノード」の減算機能のみを実行し、ルートノードを減算するため、サブノードを引き出して「hip」の構造を再調整する必要がある

ヒップホップ(Heap)実施(最大ヒップホップ)

Insertメソッド

最大臀部に要素を追加する方法を実現するには、以下の手順に注意してください.
1.ツリーの最後に追加する値を一時的に保存します(親ノードよりも大きい場合があります).
2.親ノードと比較して大きい場合は、親ノードの位置を置き換えます
次のようにコードで実装されます.

class MaxHeap:

    def __init__(self):
        self.data = [None]


    def insert(self, item):
        self.data.append(item)                      # 임시로 삽입
        i = len(self.data) - 1                      # 임시로 넣은 놈의 인덱스 구해서

        while i != 1:                               # 임시로 넣은 놈을 1번 인덱스까지 비교
            parent_i = i//2                         # 임시로 넣은 놈의 부모 노드 인덱스 구하고
            if self.data[parent_i] < self.data[i]:  # 임시로 넣은 놈이 부모 보다 클 경우 > 값 변경해야함
                self.data[parent_i], self.data[i] = self.data[i], self.data[parent_i]
                i = parent_i
            else:
                break

親ノードのサイズとの比較最大回数はlognです.
したがって,hipにおける要素付加演算に対してBigO NotationはO(logN)といえる.

removeメソッド

* 힙에서의 원소 삭제는 최대값(루트노드)를 꺼내는 pop의 개념이다.最大お尻から要素を削除する方法を実現するには、以下のことを覚えておいてください.

の最大値は、常にルートノードにあります.

ノードが空のツリーは正常なツリーではなく、削除後に再調整する必要があります.

ルートノードを削除するツリーの構造再調整は、次の手順に従います.

ツリーの最後のノードを空のルートノードの位置に配置します(最大値のルートノードが取り出されているため、ルートノードが空になり、最後のノードが空のルートノードに入ります).

一時的にルートノードに割り当てられた最後のノードとルートノードの2つのサブノード値を比較することで、構造を再調整します.

この場合、サブノード(2つのノードのみ)がない場合があります.

人の子供、

人

には2人の子供がいるかもしれません.

したがって、サブノードの値を一時的に割り当てられた値のルートノードの値と比較して、構造を再調整する必要があります.下図を参照してください.
構造再調整の過程が複雑であるため,個別の関数を減算して実現した.
詳細はコード内のコメントに書きます.

class MaxHeap:

    def __init__(self):
        self.data = [None]

    def remove(self):
        if len(self.data) > 1:
            self.data[1], self.data[-1] = self.data[-1], self.data[1]   # 맨 마지막 노드와, 루트 노드 위치 교환
            data = self.data.pop(-1)                                    # 맨 마지막 노드 삭제 후 반환
            self.max_heapify(i=1)                                       # 1번 인덱스부터 구조 적합도를 확인해 내려가는 힙 구조 재조정 함수 실행
        else:
            data = None
        return data

    def max_heapify(self, i):
        left = i * 2                                                    # 루트 노드의 왼쪽 자식
        right = i * 2 + 1                                               # 루트 노드의 오른쪽 자식
        biggest = i                                                     # 특정 범위 서브 트리의 최대값을 담을 변수
    
        # 왼쪽 자식 노드가 있으며, 그 자식 노드가 현 서브 트리의 루트 노드보다 클 때
        if len(self.data)-1 >= left and self.data[left] > self.data[biggest]:
            # 그 서브 트리의 최대값을 "루트 노드" -> "왼쪽 자식 노드" 로 변경한다.
            biggest = left
        
        # 그 후, 오른쪽 노드도 같은 방식으로 확인하며, 오른쪽 노드가 왼쪽 노드보다 클 때,
        if len(self.data)-1 >= right and self.data[right] > self.data[left]:
            # 그 서브 트리의 최대값을 "루트노드(바로 위의 if절을 안탔을경우)"나, "왼쪽 자식 노드(바로 위의 if절을 탔을경우)"가 아닌 
            # -> "오른쪽 자식 노드" 로 변경한다.
            biggest = right
        
        # 가장 큰 값(biggest)이 루트노드(i)의 위치에 올 때 까지 이 함수를 재귀적으로 호출한다.
        if biggest != i:
            self.data[biggest], self.data[i] = self.data[i], self.data[biggest]
            self.max_heapify(biggest)

上記hipの要素削除演算では,削除後に再調整するために2つのサブノードを比較する必要があるため,2*lognの時間がかかる.
これをBigO Notationとして以下に示す.O(logN)

実装が容易な方法

上記の複雑に見える抽象的な資料構造は、Pythonが独自に実現している.
https://docs.python.org/ko/3/library/heapq.html
実際,上記の内蔵モジュールによりheapデータ構造を容易にインポートして使用することができる.

ヒップホップ利用

優先順位キューでの適用

要素を挿入するときは、最大値の要素を一番前に置きます.
要素を減算する場合、その要素の特徴は次のとおりです.
hipは、優先順位キューを実現するのに最も適したデータ構造である.
hipを用いた優先キュー演算は、以下の時間的複雑さを有する.
計算時間の複雑さの説明に従ってinserto(logn)ソートを行い、最大値をルートノードに入れる必要があります.removeO(logn)ルートノードを削除すると、ツリー構造を再調整する必要があります.

ソートでの使用

値の抽出と減算では、最大値(または最小値)が常にルートノードにあるプロパティを使用してソートできます.
1.並べ替えられていない要素を最大臀部に挿入する:O(logN)2.挿入完了後、臀部が空くまで1つ取り出します:O(logN)3.取り出し順に並べます.
この場合、時間の複雑さは次のようになります.O(logN)