お尻の位置合わせ

ヒップソートは、ソートしたいデータを最小ヒップ/最大ヒップに変換するアルゴリズムです。

🎫 スタックの概念

お尻は完全バイナリツリーの形態に基づいています.特に優先順位を利用する場合に使用します.また、所与のデータのインデックスを配列として利用することができる.
hip構造には最小と最大hipの2種類があり、最小hipは親ノードが子ノード以下であることを示し、最大hipは親ノードが子ノード以上であることを示す.hipのタイプに応じて、親ノードと子ノードのサイズを比較し、hipの性質を満たすために位置を変更します.これを癒しと言います.
資料構造なので、挿入や削除の演算ができるはずです.
≪挿入|Insert|emdw≫:最後の空き領域の一番左の位置に挿入し、下から上へのheapify演算で親ノード(兄弟ノードではなく)とサイズを比較して並べ替えます.
削除:ルートノードを削除し、最後のレベルの最後の値を空のルートノードに挿入し、上から下へheapify演算を行います.

数値の例

https://ratsgo.github.io/data%20structure&algorithm/2017/09/27/heapsort/
リファレンス

💻 ヒップ挿入削除コード(python)の実装

https://airsbigdata.tistory.com/146
リファレンス

時間の複雑さ

heapify時間複雑度:最悪の場合、ツリーの高さ(log 2 N)に応じて、すべてのノードの値を比較する必要があります.値を比較または置換する動作はO(1)であるため、O(logn)
挿入・削除の時間複雑度:挿入・削除に必要な演算O(1)、heapifyに必要な時間はO(logn)であるため、O(logn)となる.
お尻を構成する時間の複雑さ:
空ヒップ上のn個の要素を順次挿入演算する必要があるのでO(nlogn)である.

🎫 スタックソートの概念

与えられた要素で最大/最小hipを作成すると、最大(最小)hipはルートノード(r)の値と最後のノード(l)の値を交換します.交換により、rは自分の位置を見つけることができ、lの新しい位置を探すためにソートされると、ルートノード上に位置する新しい値new rは、古いルートノード値rを除くこのhip構造の中で最大(小さい)の値となる.このように繰り返すと、ソートが形成されます.

数値の例

https://ratsgo.github.io/data%20structure&algorithm/2017/09/27/heapsort/
リファレンス

💻 お尻の位置合わせコード(python)を実現

def heap_sort(unsorted):
    n = len(unsorted)
    #최대 힙 만들기
    #최소힙은 부등호만 반대로 바꿔주면 됨
    for i in range(1, n):
        child = i
        while child != 0:
            parent = (child-1)//2
            if unsorted[parent] < unsorted[child]:
                unsorted[parent], unsorted[child] = unsorted[child], unsorted[parent]
            child = parent #최대값이 루트까지 도달 할 수 있도록

    #힙 만들기
    for node in range(n-1, -1, -1):
        #루트 노드와 마지막 노드를 교환
        #값이 큰 순서대로 힙의 끝에 저장됨
        unsorted[0], unsorted[node] = unsorted[node], unsorted[0]
        parent = 0
        child = 1

        # 정렬이 미완료 된 노드들 사이에서
        # 마지막 노드 자리리 보내준 루트 노드를 제외한 가장 큰 값을 찾고
        # 루트 노드 자리로 온 마지막 노드의 자리 찾기
        while child < node:
            child = parent*2 + 1
            #마지막 노드 자리로 보낸 루트 노드를 제외한 가장 큰 노드를 찾기 위해
            if child < node-1 and unsorted[child] < unsorted[child+1]:
                child += 1
            #마지막 노드 자리로 보낸 루트 노드를 제외한 가장 큰 노드를 루트 자리로 보내기 위한 과정
            if child < node and unsorted[parent] < unsorted[child]:
                unsorted[parent], unsorted[child] = unsorted[child], unsorted[parent]

            parent = child

    return unsorted



if __name__ == '__main__' :
    arr = list(map(int, input().split()))
    print(heap_sort(arr))

時間の複雑さ

まず、お尻を作る複雑さはO(n)です.そして、n個の要素を大きさ順にheapifyしなければならないので、O(nlogn)となる.
従って、O(n)+O(nlogN)=O(nlogN)となる.