[データ構造]スタック

優先キューに作成されたデータ構造

0 Intro

資料構造削除順序スタックが最後に入った優先削除.Q先に入ったものは削除するまず、優先度が最も高いキューを削除します.

優先キュー?
データにはこの優先度があり、優先度の高いデータが優先されます.

優先キュー使用例
シミュレーションシステム、ネットワークトラフィック制御、オペレーティングシステムスケジューリング

優先度は、アレイ、接続リスト、hipによって実現することができるが、힙を使用するとより効果的である.

1定義

完全バイナリツリーの一種で、優先キューに作成されるデータ構造です.

の複数の値の中で最も高い値または最も高い値が速い資料構造

半並べ替え状態(緩和並べ替え)

親ノード優先、子ノード優先

HIPツリーは重複値を許可します(バイナリプローブツリーは重複値を許可しません).

最大臀部、最小臀部

2実施

hipを格納する標準的な資料構造は配列されている.

を容易に実現するために、バエルの最初のインデックス0は使用できません.

ヒップホップにおける親ノードと子ノードの関係

左サブインデックス=親インデックス*2

右サブインデックス=親インデックス*2+1

親インデックス=子インデックス/2

2-1ヒップを挿入

最初にhipの最後のノードに新しい

を挿入する

の新しいノードとその親ノードの優先度を比較することによって、hop
ex)最大臀部に新しい要素を挿入する8

2-2ヒップを削除

の優先度が最も高いのはルートノードです.ルートノードの要素を削除します.

削除されたルートノードはhipの最後のノード要素にインポートされます.

最大お尻から最高値を削除します.

3コード

Pythonは統合heapqを提供しています.

最小臀部

import heapq

heap = []

heapq.heappush(heap,2)
heapq.heappush(heap,1)
heapq.heappush(heap,5)
heapq.heappush(heap,7)
heapq.heappush(heap,4)
heapq.heappush(heap,9)
# [1,2,4,5,7,9] 의 힙구조

最大のヒップホップ機能

を提供

arr = [1,2,4,5,7,9]
heap=[]
for a in arr:
  heapq.heappush(heap,-a)
while heap:
  print(heapq.heappop(heap)*-1)