アルゴリズムベースヒップホップリソース構造

37954 ワード

algorithm テキストリンク

🌈 ヒップホップ

🔥 お尻って何?

🔥 バイナリナビゲーションツリーとheapの異同

🔥 heapにデータを挿入する

🔥 データをheapに削除

🔥 練習問題を積み上げる.

1.お尻とは?

heapは、最大値および最小値を迅速に検索するために設計された完全なバイナリツリー

である.

アレイにデータを挿入し、最大値と最小値を検索するにはO(n)の時間的複雑度が必要であり、スタック内で最大値と最小値を検索する場合、時間的複雑度はO(logn)、すなわち

である.

、すなわち、優先キューなどの最大値または最小値を迅速に検索する必要がある場合にheap

を使用する.

heapは構造Max heap(最大heap)に分けて最大値と最小heap(最小heap)を求める最小値

を求める.

heapには2つの条件があります.

Parentノードの値は、常にChildノードの値に等しいか、またはそれより大きい.(最大お尻)

最小臀部の上部ノード値は最小であり、最大臀部の上部ノード値は最大である

は完全なバイナリツリー型

を有する.

2.バイナリナビゲーションツリーとheap(完全バイナリツリー)の異同

1）共通点

heapもバイナリナビゲーションツリーもバイナリツリー

2）違い

heapは、各ノードの値がサブノード(Max heapの場合)の

以上であることを示す.

バイナリナビゲーションツリーの左側のサブノード値が最小で、次に親ノード値が小さく、右側のサブノード値が最大です.

親ノードの値よりも小さいノードが左側に挿入する、大きいノードが右側に挿入されるため、

heapバイナリナビゲーションツリー条件下のサブノードには、小さな値が左、大きな値が右の条件は存在しません.

のサイズを比較せず、左から値を挿入してバイナリ形式を区切る

目的が違う

バイナリナビゲーションツリーはナビゲーションのための構造として理解することができ、hipは最大/最小値検索のための構造の1つとして理解することができる

3.heapにデータを挿入する

HIPは完全バイナリツリーで、最初のデータを挿入するとRoot Node

になります.
追加の

データを挿入すると、左側ノードが存在するかどうかを判断し、存在しない場合は左側ノードに入れる;右側ノードがすでに存在する場合は右側ノードに移動し、存在しない場合は

に入れる.

の右側ノードに移動する場合は、もう一度左側ノードの子供が存在するかどうかを確認し、左側から

を挿入します.

Swapの方法は、挿入ノードの値を親ノードの値と比較する、挿入ノードの値がより大きい場合は、大きくならないまでSwap(Max Heap)

を継続する.

、すなわち完全バイナリツリーの規則に従って左から位置決めし、挿入位置で自分の値を親ノードの値と比較し、最後にSwapボックス

、

HIPを実装する場合、通常は配列を使用し、スタック実装を容易にするため、ROOT NODEインデックス番号を1に指定して実装を簡略化する(空インデックスは0)

親ノードインデックス番号は、子ノードインデックスを2で割ったものに等しい
🔍 parent node's index = child node's index//2

左側の子ノードインデックス番号は、親ノードインデックス番号に2を乗じたものに等しい
🔍 left child node's index = parent node's index * 2

右サブノードインデックス番号は、親ノードインデックス番号に2を乗じた後+1に等しい
🔍 right child node's index = (parent node's index * 2) + 1

# heap 데이터 삽입
class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None) # 맨 앞에 요소는 None으로 채움
        self.heap_array.append(data)
    def move_up(self, inserted_idx):
        if inserted_idx <= 1: # inserted_idx가 Root Node일 경우
            return False
        parent_idx = inserted_idx // 2
        # inset한 Node의 값이 insert한 Node의 parent의 Data값 비교
        if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
            return True
        else:
            return False
    # 완전 이진트리의 규칙으로 배열에 Node 값 삽입
    def insert(self, data):
        if len(self.heap_array) == 0:
            self.heap_array.append(None)
            self.heap_array.append(data)
            return True
        self.heap_array.append(data)
        # Swap
        inserted_idx = len(self.heap_array) - 1 # 최근 추가된 데이터의 index 번호
        # move_up 매서드에 inserted_idx값을 전달하였을 때, True가 return되면 계속 반복
        while self.move_up(inserted_idx): 
            parent_idx = inserted_idx // 2
            self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx] # swap
            inserted_idx = parent_idx
        return True
# 데이터 삽입 확인        
heap = Heap(15)
print(heap.heap_array) # [None, 15]
heap.insert(10)
print(heap.heap_array) # [None, 15, 10]
heap.insert(8)
print(heap.heap_array) # [None, 15, 10, 8]
heap.insert(5)
print(heap.heap_array) # [None, 15, 10, 8, 5]
heap.insert(4)
print(heap.heap_array) # [None, 15, 10, 8, 5, 4]
heap.insert(20)
print(heap.heap_array) # [None, 20, 10, 15, 5, 4, 8]

4.heapにデータを削除する

通常heapから最短ノード(Root Node)

を削除する.

heapの用途は、最大値または最小値をルート上に配置し、

のため、直ちに取り出して書き込むことである.

最上位でデータを削除するとき、最後に追加するノードをRootノードに移動し、ParentノードをChildノードの値と比較し、Swapを

に設定する.

Swapタスクは2つのRootノードのサブノードを比較し、より高い値とSwap(2つの大きな値)

を得た.

は、このSwapタスクを、子ノードが存在しない場合、または親ノードが子ノードより大きい場合まで処理し、子ノードの存在に応じて3つのケースに分割する.

case 1:左側のサブノードがない場合(すべてのサブノードがないことを示す)

csee 2:左側のサブノードのみ(右側のサブノードなし)

csee 3:左、右サブノードともに

# heap 데이터 삭제
class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)
    def move_up(self, inserted_idx):
        if inserted_idx <= 1: # inseted_inx가 Root Node일 경우
            return False
        parent_idx = inserted_idx // 2
        # inset한 Node의 값이 inset한 Node의 parent의 Data값 비교
        if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
            return True
        else:
            return False
    # 완전 이진트리의 규칙으로 배열에 Node 값 삽입
    def insert(self, data):
        if len(self.heap_array) == 0:
            self.heap_array.append(None)
            self.heap_array.append(data)
            return True
        self.heap_array.append(data)
        # Swap
        inserted_idx = len(self.heap_array) - 1 # 최근 추가된 데이터의 index 번호
        # move_up 매서드에 inserted_idx값을 전달하였을 때, True가 return되면 계속 반복
        while self.move_up(inserted_idx): 
            parent_idx = inserted_idx // 2
            self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx] # swap
            inserted_idx = parent_idx
        return True
    # Root Node 삭제
    def move_down(self, poped_idx):
        left_child_poped_idx = poped_idx * 2
        right_child_poped_idx = poped_idx * 2 + 1
        # case1 : 왼쪽 자식 노드가 없을때(자식 Node가 모두 없다는 의미)
        if left_child_poped_idx >= len(self.heap_array):
            return False
        # csee2 : 왼쪽 자식 노드만 있을 때(오른쪽 자식 노드는 없음)
        elif right_child_poped_idx >= len(self.heap_array):
            if self.heap_array[poped_idx] < self.heap_array[left_child_poped_idx]:
                return True # 자식이 더 클 때는 Swap(While문 실행)
            else:
                return False
        # csee3 : 왼쪽, 오른쪽 자식 노드가 모두 있을 때
        else:
            if self.heap_array[left_child_poped_idx] > self.heap_array[right_child_poped_idx]:
                if self.heap_array[poped_idx] < self.heap_array[left_child_poped_idx]:
                    return True
                else:
                    return False
            if self.heap_array[left_child_poped_idx] < self.heap_array[right_child_poped_idx]:
                if self.heap_array[poped_idx] < self.heap_array[right_child_poped_idx]:
                    return True
                else:
                    return False
    def pop(self):
        # Node가 없거나(비어있는 이진 트리), Root Node만 있는 경우
        if len(self.heap_array) <= 1: 
            return None
        returned_data = self.heap_array[1] # 첫번째 Node의 값(Root Node의 value)
        # Swap
        self.heap_array[1] = self.heap_array[-1] # 마지막 데이터를 Root Node로 교체
        del self.heap_array[-1] # Root Node로 이동했기 때문에 삭제
        poped_idx = 1
        while self.move_down(poped_idx): # move_down 메서드를 통해 True를 반환 받으면 반복문 실행
            left_child_poped_idx = poped_idx * 2
            right_child_poped_idx = poped_idx * 2 + 1
            # csee2 : 왼쪽 자식 노드가 있을 때
            if right_child_poped_idx >= len(self.heap_array):
                if self.heap_array[poped_idx] < self.heap_array[left_child_poped_idx]:
                    self.heap_array[poped_idx], self.heap_array[left_child_poped_idx] = self.heap_array[left_child_poped_idx], self.heap_array[poped_idx]
                    poped_idx = left_child_poped_idx
            # csee3 : 왼쪽, 오른쪽 자식 노드가 모두 있을 때
            else:
                if self.heap_array[left_child_poped_idx] > self.heap_array[right_child_poped_idx]:
                    if self.heap_array[poped_idx] < self.heap_array[left_child_poped_idx]:
                        self.heap_array[poped_idx], self.heap_array[left_child_poped_idx] = self.heap_array[left_child_poped_idx], self.heap_array[poped_idx]
                if self.heap_array[left_child_poped_idx] < self.heap_array[right_child_poped_idx]:
                    if self.heap_array[poped_idx] < self.heap_array[right_child_poped_idx]:
                        self.heap_array[poped_idx], self.heap_array[right_child_poped_idx] = self.heap_array[right_child_poped_idx], self.heap_array[poped_idx]
        return returned_data
# 데이터 삽입 확인        
heap = Heap(15)
heap.insert(10)
heap.insert(8)
heap.insert(5)
heap.insert(4)
print(heap.heap_array) # [None, 15, 10, 8, 5, 4]
heap.insert(20)
print(heap.heap_array) # [None, 20, 10, 15, 5, 4, 8]
# 데이터 삭제 확인
heap.pop()
print(heap.heap_array) # [None, 15, 10, 8, 5, 4]
heap.pop()
print(heap.heap_array) # [None, 10, 4, 8, 5]
heap.pop()
print(heap.heap_array) # [None, 8, 4, 5]

5.練習問題を積む

1)BOJ 1715:ソートカード(https://www.acmicpc.net/problem/1715 )

PriorityQueueは、put()で挿入するget()で抽出されたHeapデータ構造ライブラリ

である.

PriorityQueueを使用すると、データの最小の開始からデータ

を順番に抽出できます.

import sys
from queue import PriorityQueue
pq = PriorityQueue()
# 삽입 : put()
pq.put(200)
pq.put(1)
pq.put(20)
pq.put(300)
pq.put(90)
pq.put(8)
pq.put(33)
# 추출 : get()
for i in range(pq.qsize()):
    print(pq.get())
"""
1
8
20
33
90
200
300
"""

は、最小の2つのカード数を抽出し、これらのカード数を加算し、PriorityQueueが空になるまで操作を繰り返す.

PriorityQueueはlen()を使用できないため、qsize()関数を使用してPriorityQueueが空になるまで繰り返します.

さらに、出力値は2つの最小の数をとり、ans変数に1つの値を加算し続け、最後に

を出力する.

# Heap
# BOJ 1715 : 카드 정렬하기
import sys
from queue import PriorityQueue
n = int(sys.stdin.readline())
pq = PriorityQueue()
for i in range(n):
    a = int(sys.stdin.readline())
    pq.put(a)
ans = 0
while pq.qsize() > 1:
    min1 = pq.get() # 가장 작은 것
    min2 = pq.get() # 그 다음 작은 것
    next = min1 + min2 
    ans += next
    pq.put(next) # 다시 넣음
print(ans)

Reference

この問題について(アルゴリズムベースヒップホップリソース構造), 我々は、より多くの情報をここで見つけました https://velog.io/@jewon119/알고리즘-기초-힙Heap

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

ダーティjQueryのアコーディオン

WebViewの初使用