データ構造、heap

💡 ブログの整理した文章をたくさん読みました.参考にしたブログには出典が残っています.
スタックの概念

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

アレイを使用してheapを実装することができる.

優先度ライブラリは、アレイ、接続リスト、hipによって実現することができる.中でもheapで実施するのが最も効果的である.

データ構造削除の要素スタックが最近入ったデータキューが最も早く入ったデータ優先度キュー(heap)が最も高いデータ
優先キュー使用例

シミュレーションシステム

ネットワークトラフィック制御

自分の操作をスケジューリング

数値解析計算

データ構造heapとは?

は、最低価格または最高価格を迅速に検索するための構造です.

臀部は反対斉状態を維持した.

より大きい値はより高いレベルにあり、より小さい値はより低いレベルを構成する.

簡単に言えば、親ノードのキー値は常にサブノードのキー値のバイナリツリーよりも大きい.

は小数を探すのに役立つようです.以下で再度説明しますが、Pythonは最小限のheapしか提供していません.最大heapを使用するためには、以下の簡単な方法を用いて実現することができる.

heapツリー重複許容値(バイナリナビゲーションツリー重複許容値)

キー値のサイズ関係は、次のとおりです. 親ノードから子ノードの間 これらは成立し、同級ノードには影響しません.

時間複雑度O(log n)

ヒープのタイプ
最大ヒープ数

親ノードのキー値が子ノードのキー値以上の完全なバイナリツリー

鍵(親ノード)≧鍵(子ノード)

Pythonのheapqモジュールは最小のhipを採用しているため、最大のhipを実現するにはいくつかのテクニックが必要です.

さいしょうスタック

親ノードのキー値が子ノードのキー値以下の完全なバイナリツリー

鍵(親ノード)≦鍵(子ノード)

スタックの実装

hipを格納標準データ構造は、タイル

である.

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

特定の場所のノード番号は、新しいノードを追加するときも変わらない.
たとえば、ルートノードの右側のノードの番号は常に3です.

そうにゅうえんざん
挿入する値

をツリーの最後の要素に追加します.

親ノードのサイズ関係を比較し、満足するまで位置を交換します.

アクションの削除

hipは、ルートノードしか削除できないため、ルートノードを削除します.

最後のノードをルートノードに移動します.

サブノードと比較して、条件が満たされるまで移動します.

お尻を追加

import heapq

# 원소를 추가하여 heap 자료형으로 만든다
heap = []

heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
heapq.heappush(heap, 3)
heapq.heappush(heap, 4)
heapq.heappush(heap, 5)

print(heap)

# 
[1, 2, 3, 4, 5]

既存のリスト

# 이미 리스트가 있는 경우
heap_2 = [5,6,9,3,5,1]

heapq.heapify(heap_2)
print(heap_2)

#
[1, 3, 5, 6, 5, 9]

最小要素を削除

# 가장 작은 요소가 삭제된다
heapq.heappop(heap_2)
print(heap_2)
heapq.heappop(heap_2)
print(heap_2)

#
[1, 3, 5, 6, 5, 9]
[3, 5, 5, 6, 9]
[5, 5, 9, 6]

最大ヒップを作る

import heapq

# 튜플의 첫 번째 인자는 우선순위, 그러나 - 형태를 띄고 있기 떄문에 
heap_items = [1,3,5,7,9]

max_heap = []
for item in heap_items:
    heapq.heappush(max_heap, (-item, item))

print(max_heap)

# heappop 사용시 가장 작은 요소를 리턴해야 한다. 하지만 우선순위를 반대로 했기 때문에 가장 큰 수가 리턴이 되는 것을 확인 가능하다. 
max_item = heapq.heappop(max_heap)
print(max_item)
# (-9, 9)

max_item = heapq.heappop(max_heap)[1]
print(max_item)
# 9

例
N個のビーカーに液体が入っています.すべてのビーカーの液体量がT以上になるまで. 液体が最も少ない2つ ビーカーの中の液体を合わせなければなりません.各ビーカーの液体量のリスト. Lと条件 すべてのビーカー量がTより大きくなるまで、Tが与えられたときに必要な動作回数を返す関数が実現される.(実装できない場合は-1を返します)

import heapq

def my_heap_example(L, T):
  """ 주어진 비커의 리스트를 힙 구조로 변환 """
  heapq.heapify(L) 

  result = 0

  while len(L) >= 2 : #IndexError 방지
      """ 힙에서 최솟값을 가져옴 """
      min_ = heapq.heappop(L) 
      
      if min_ >= T: # 액체의 최솟값이 T보다 크다는 조건 만족(종료)
        print("-"*40, "\nresult:", result)
        return result 
        
      else: # 두 번째로 작은 값 가져와서 합친 값을 힙에 삽입
        min_2 = heapq.heappop(L) 
        heapq.heappush(L, min_ + min_2)
        result += 1
        print("step{}: [{},{}] 합칩".format(result, min_ , min_2))
        print("       →", L)
  
  
  if L[0] > T:
    print("-"*40, "\nresult:", result)
    return result
    
  else:
    print("-"*40, "\nMission Failed")
    return -1

# 
step1: [1,2] 합칩
       → [2, 3, 6, 4, 5, 7, 9, 8]
step2: [2,3] 합칩
       → [4, 5, 5, 8, 9, 7, 6]
---------------------------------------- 
result: 2
2

プログラマのよりマップの解法
1.最初の失敗

import heapq

def solution(scoville, K):
    
    answer = 0
    heapq.heapify(scoville)
    
    while len(scoville) >= 1:
        min_scoville_1 = heapq.heappop(scoville)
        
        if min_scoville_1 >= K:
            return answer
        
        else:
            min_scoville_2 = heapq.heappop(scoville)
            heapq.heappush(scoville, (min_scoville_1 + min_scoville_2 * 2))
            answer += 1
        
    return answer

運転時エラー→効率テスト問題

2.プログラマレポートで修正した部分

import heapq

def solution(scoville, K):
    
    answer = 0
    heapq.heapify(scoville)
    
    while scoville[0] <= K: <- 이 부분 수정
        min_scoville_1 = heapq.heappop(scoville)
        
        if min_scoville_1 >= K:
            return answer
        
        else:
            min_scoville_2 = heapq.heappop(scoville)
            heapq.heappush(scoville, (min_scoville_1 + min_scoville_2 * 2))
            answer += 1
        
    return answer

heapqが有効な場合はheapifyでheapを作成し、sortが有効な場合はheapifyと同じであるため、ソートするだけでよい.
最も重要なのはwhileを条件としたmin(scoville)です
最適な値を見つけるために配列全体をナビゲートする必要があるためかもしれません.
heappushを作ると、最高価格が一番前に並んでいて、scoville[0]だけでいいことがわかります.
(Python内蔵heapqは最小のお尻なので、その価格は最高になります)
聞いてまた直して、効率テストは再び失敗しました.何か問題がありますか.
問題は、「すべての食べ物のスコビル指数をKより大きくすることができない場合は、-1を返します.」この条件も考慮しなければならない.
3.問題の最終通過

def solution(scoville, K):

    answer = 0
    heapq.heapify(scoville)

    while len(scoville) >= 2:
        min_scoville_1 = heapq.heappop(scoville)

        if min_scoville_1 >= K:
            return answer

        else:
            min_scoville_2 = heapq.heappop(scoville)
            heapq.heappush(scoville, (min_scoville_1 + min_scoville_2 * 2))
            answer += 1

    if scoville[0] < K:
        return -1

    return answer

の最初の失敗では、while len(scoville) >= 2:の部分で失敗したと思います.最小値と最小値未満の値は、リストに少なくとも2つの値がある必要があるため、この場合はエラー(不確定)になる可能性があります.if scoville[0] < K:\ return -1という部分も追加されました.問題にはすでに모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다の条件があるが、これらの条件を無視して問題を解決しようとしたため、エラーが発生した.

Reference
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html:hipの概念を参照した.
https://hocheon.tistory.com/70:hipの概念を参照した.
https://littlefoxdiary.tistory.com/3:Hipの概念、例など.