優先キュー


これは、最も優先度の高いデータを最初に削除するデータ構造です.
例えば、複数の物品データを資料構造に入れ、価値の高い物品データから取り出して確認する必要がある場合は、優先順位キューを使用することができる.
スタックの最後に挿入されたデータ
キューに最初に挿入されたデータ
優先度キューで最も優先度の高いデータ
ヒップホップ
優先順位キューを実装するためのデータ構造の1つ
最小臀部(Min Heap)と最大臀部(Max Heap).
複数の最短パスアルゴリズムを含む複数のアルゴリズムで使用される.
優先キュー実装挿入時間削除時間リストO(1)O(N)Hip(Heap)O(logn)O(logn)
hipライブラリの使用例:最小hip
import heapq
# 오름차순 힙 정렬(Heap Sort)
def heapsort(iterable):
	h = []
	result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
    	heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
    	result.append(heapq.heappop(h))
    return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

실행결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
hipライブラリの使用例:最大hip
import heapq

# 내림차순 힙 정렬(Heap Sort)
def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, -value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(-heapq.heappop(h))
    return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

실행결과
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]