📍 お尻

英語の単語heapは「たくさんのもの」を意味します.
hipは、最高価格と最高価格を迅速に検索するための完全なバイナリツリーに基づくデータ構造です.
注)フルバイナリツリー:ツリーの上から下、左から右に順に埋め込まれたバイナリツリー
(最終レベルは含まれません)
AがBの親ノード(親ノード)である場合、属性、すなわちAのキー値とBのキー値との間にサイズ関係が存在する.
注)兄弟間の不確定な大文字と小文字の関係
2種類のお尻
1.最大臀部:親ノードのキー値が常に子ノードのキー値より大きい臀部
2.最小臀部:親ノードのキー値が常に子ノードのキー値より小さい臀部
HIPでは、優先度が最も高い(または最も低い)ノードは常にルートノードに到達する.
=>優先キューなどの抽象データ型を実装できます.

🔹 ヒップ

Python heapqモジュールはheapq(優先キュー)アルゴリズムを提供する
バイナリツリーベースの最小スタックデータ構造の提供

import heapq # 모듈 임포트
# 파이썬의 보통 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와줌

heap = [] 
heapq.heappush(heap, 1) # 노드 추가: heappush 메소드 이용
heapq.heappush(heap, 7)

return heapq.heappop(heap) # 노드 삭제: heappop 메소드 이용 (가장 작은 원소를 꺼내어 리턴, 자동적으로 그 다음으로 작은 원소가 루트노트가 됨)
print(heap[0]) # 최소값을 꺼내지 않고 리턴만 하려면 인덱스로 접근하기

tmp = [7, 5, 8, 3]
heapq.heapify(tmp) # 기존에 사용한 리스트를 힙으로 변환: heapify 메소드 이용, 시간 복잡도는 O(N)

🔹 適用

最大ヒップ

# 힙에 튜플(tuple)을 원소로 추가하거나 삭제하면, 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용

# 각 값에 대한 우선 순위를 구한 후,
# (우선 순위, 값) 구조의 튜플(tuple)을 힙에 추가하거나 삭제하면 됨
# 그리고 힙에서 값을 읽어올 때는 각 튜플에서 인덱스 1에 있는 값을 취하면 됨
import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
    heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
    print(heapq.heappop(heap)[1])  # index 1

# 결과
# 8
# 7
# 5
# 4
# 3
# 1    

K番目の最小値/最大値

# 주어진 배열로 힙을 만든 후, heappop() 함수를 K번 호출
import heapq

def kth_smallest(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)

    kth_min = None
    for _ in range(k):
        kth_min = heapq.heappop(heap)
    return kth_min

print(kth_smallest([4, 1, 7, 3, 8, 5], 3))

# 결과
# 4

お尻の位置合わせ

import heapq

def heap_sort(nums):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)

    sorted_nums = []
    while heap:
        sorted_nums.append(heapq.heappop(heap))
    return sorted_nums

print(heap_sort([4, 1, 7, 3, 8, 5]))

# 결과
# [1, 3, 4, 5, 7, 8]

📍 優先キュー

優先キューは通常のキューやスタックに似ていますが、各要素には優先度があります.
優先度の高い要素は、優先度の低い要素より優先されます.
(2つの要素の優先度が同じ場合はqueueの順に処理します)
注意)ヒント:要素は先入先出順で処理する
参考)優先順位Qはhip?(X)
優先順位キューは、リストやマッピングなどの抽象概念です.
リストがリストまたは配列を接続することによって実現できるように、優先キューはhipまたは他の方法で実現することができる.

🔹 実装方法:配列、接続リスト、hip

実装方法enqueue()dequeue()配列O(1)O(N)接続リストO(1)O(N)ソート配列O(N)O(1)ソート接続リストO(N)O(1)ヒップホップ(logn)O(logn)
最悪の場合、ヒップホップはO(logN)を保証できるので、通常ヒップホップを採用しています