お尻の位置合わせ
ヒップソートは、ソートしたいデータを最小ヒップ/最大ヒップに変換するアルゴリズムです。
🎫 スタックの概念
お尻は完全バイナリツリーの形態に基づいています.特に優先順位を利用する場合に使用します.また、所与のデータのインデックスを配列として利用することができる.
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)となる.
Reference
この問題について(お尻の位置合わせ), 我々は、より多くの情報をここで見つけました https://velog.io/@yuyeon/힙-정렬テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol