Heap Sort

17327 ワード
テキストリンク
heap sortはhip特性を用いてソートするアルゴリズムである
hipは、親値が常に子値より大きい条件を満たすバイナリツリーです.
  • お尻の一番上の根はお尻の中で最も価値のある
    • です.
  • 兄弟ノード間の大小関係を問わない
    • お尻を構成するときのポイント
    要素a[i]で
    親:a[(i-1)/2]
    左サブアイテム:a[i*2+1]
    右サブアイテム:a[i*2+2]
    ルート削除ヒップホップの再構成

    1.お尻からルート10を取り出し、お尻の最後の要素1を10ビットに移動する
    2.1を知って位置に移動し、移動する1の2人の子供は9と5なので、1、9、5の中で一番値が9なので、9と位置を変えます
    3、1、8、3から8まで最大で、第8課は席を変えます
    4.1、6、7から7は1番目に大きいので、位置を変えます

    コード#コード#


    Heap設定
    1.最初のインデックスから設定を開始するので、0番目のノードはNoneのままにします.
    class Heap:
    def __init__ (self,data):
        self.heap_array=list()
        self.heap_array.append(None) #인덱스는 1부터 시작
        self.heap_array.append(data)
  • 追加するノードを親ノードと比較し、子ノードが親ノードより大きい場合はmove up関数実装
    • を使用してTrueを返します.
        def move_up(self,inserted_idx): #노드의 위치를 판별
        if inserted_idx <=1:
            return False
        
        parent_idx = inserted_idx//2
        if self.heap_array[inserted_idx]>self.heap_array[parent_idx]:
            return True
  • 挿入関数の実装
    例外処理挿入するノードが最初のノードの場合は、0番の面インデックスにNoneを追加します.
    挿入に必要な条件:ノードを先頭に配置する要素
    最後にmove up関数により、親ノードが親ノードより大きい場合、親ノードと位置を交換できる関数が実現される:
        def insert(self,data):
     if len(self.heap_array) == 0:
         self.heap_array.append(None)
         self.heap_array.append(data)
         return True
     
     self.heap_array.append(data)
     
     inserted_idx=len(self.heap_array) - 1
     while self.move_up(inserted_idx): #바꿔줘야 할 노드이면 계속해서 바꿀 수 있게
         parent_idx = inserted_idx//2
         self.heap_array[inserted_idx],self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
         inserted_idx=parent_idx
     return True
    • 4.削除関数の実装
    削除は本当に昨日の木のように難しいです.
    空気を密にし,すべての状況が発生しないようにしなければならない.
    削除の場合:
    1.一番前のルートノードと一番後ろのノードの位置を変更する
    2.サブノードの右側と左側に比べて、より大きな値を持つノードと位置を交換します.
    3.ポイント位置を下に移動する場合
    1)サブノードがない場合
    2)右側ノードのみの場合
    3)左ノードのみの場合
    考えながら下りていく
        def move_down(self,popped_idx):
        left_child_popped_idx=popped_idx*2
        right_child_popped_idx=popped_idx*2+1
        if left_child_popped_idx>=len(self.heap_array): #자식노드가 없을 때
            return False
        elif right_child_popped_idx>=len(self.heap_array):
            if self.heap_array[popped_idx]<self.heap_array[left_child_popped_idx]:
                return True
            else:
                return False
        else:
            if self.heap_array[left_child_popped_idx]>self.heap_array[right_child_popped_idx]:
                if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                    return True
                else:
                    return False
            else:
                if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
                    return True
                else :
                    return False

    def pop(self):
        if len(self.heap_array) <=1:
            return None
        returned_data = self.heap_array[1]
        self.heap_array[1]=self.heap_array[-1]
        del self.heap_array[-1]
        popped_idx=1

        while self.move_down(popped_idx):
            left_child_popped_idx=popped_idx*2
            right_child_popped_idx=popped_idx*2+1

            if right_child_popped_idx >= len(self.heap_array):
                if self.heap_array[popped_idx]<self.heap_array[left_child_popped_idx]:
                    self.heap_array[popped_idx],self.heap_array[left_child_popped_idx]=self.heap_array[left_child_popped_idx],self.heap_array[popped_idx]
                    popped_idx = left_child_popped_idx
            else:
                if self.heap_array[left_child_popped_idx]>self.heap_array[right_child_popped_idx]:
                      self.heap_array[popped_idx],self.heap_array[left_child_popped_idx]=self.heap_array[left_child_popped_idx],self.heap_array[popped_idx]
                      popped_idx = left_child_popped_idx
                else:
                    if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
                        self.heap_array[popped_idx],self.heap_array[right_child_popped_idx]=self.heap_array[right_child_popped_idx],self.heap_array[popped_idx]
                        popped_idx=right_child_popped_idx
        return returned_data
    単一チェーンテーブル(class)
    [Node JS]登録会員はインバウンド登録1/MongoDB mongose接続/を実施する.Envファイル