22課概要

データを挿入し、お尻の位置合わせを維持します.

22課の内容

お尻って何?

バイナリツリー
1.ルートノードは常に最高値または最高値を有する
-最大ヒープ(max heap)、最小ヒープ(min heap)
2.完全バイナリツリーでなければなりません

ツリーをアレイで表示

お尻は常に完全なバイナリツリーでなければならないので、平らにして実施するのに便利です.完全バイナリツリーは、낮은 레벨から始まり、次いで왼쪽から順次記憶されるので、연속の記憶空間を有することができる.これは、アレイとして簡単に表現できることを意味します.

要素の挿入

insert(self,itme)-要素を挿入
要素を挿入した後も、ヒップを維持するために位置合わせする必要があります.

最後に新しい要素

を挿入する

の親ノードと比較する値が大きい場合は、

を親ノードと置換する.

def insert(self, item):
        m = len(self.data)
        self.data.append(item)
        
        if m == 1: #빈 리스트일때 0은 None이므로 에러
            return
        
        while self.data[m//2] < self.data[m]: #값이 클때 까지
            self.data[m], self.data[m//2] = self.data[m//2], self.data[m] #치환
            m = m // 2 #상위 레벨로
            if m == 1: #루트노드면 종료
                break

質問する

class MaxHeap:

    def __init__(self):
        self.data = [None]


    def insert(self, item):
        m = len(self.data)
        self.data.append(item)
        
        if m == 1: #빈 리스트일때 0은 None이므로 에러
            return
        
        while self.data[m//2] < self.data[m]: #값이 클때 까지
            self.data[m], self.data[m//2] = self.data[m//2], self.data[m] #치환
            m = m // 2 #상위 레벨로
            if m == 1: #루트노드면 종료
                break

def solution(x):
    return 0

23概要

ヒップ内要素を削除して並べ替え

23話の内容

hipの削除は常にルートノードを削除します.ただし、完全なバイナリツリーを保持する必要があるため、最後のノードと交換およびソートする必要があります.

ルートノードを削除し、最後のノードと交換

remove(self)-ルートノードを削除して置き換えます.

	def remove(self):
        if len(self.data) > 1:
            self.data[1], self.data[-1] = self.data[-1], self.data[1]
            data = self.data.pop(-1)
            self.maxHeapify(1)
        else:
            data = None
        return data

len(self.data)を使用して、ツリーが空であるかどうかを確認します.空でない場合は、ルートノードと最後のノードを交換した後に最後のノードを削除します.次いで、maxHeapify()を呼び出して臀部を整列させる.

お尻の位置合わせ

削除および変換中にルートノードの後に最大のノードが最後のノードである場合は構いませんが、そうでない場合はhipを保持できません.そのため、ソートが必要です.挿入とは対照的に、루트부트 말단노드方向でサブアイテムのサイズと自身を比較します.

	def maxHeapify(self, i):
        # 왼쪽 자식 (left child) 의 인덱스를 계산합니다.
        left = i * 2

        # 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
        right = i * 2 + 1

        smallest = i
        # 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if left < len(self.data) and self.data[smallest] < self.data[left]:
            # 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다.
            smallest = left

        # 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if right < len(self.data) and self.data[smallest] < self.data[right]:
            # 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다.
            smallest = right

        if smallest != i:
            # 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
            self.data[i], self.data[smallest] = self.data[smallest], self.data[i]

            # 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
            self.maxHeapify(smallest)

left人の子供とright人の子供のうち、残りの漢字式と自分より年上の子供がいる場合は置き換えます.オブジェクトやリンクを使用するツリーとは異なり、配列を使用する場合は存在するかどうかを確認する必要があるため、サイズがlen(self.data)を超えているかどうかを確認できます.

質問する

class MaxHeap:

    def __init__(self):
        self.data = [None]
        
    def remove(self):
        if len(self.data) > 1:
            self.data[1], self.data[-1] = self.data[-1], self.data[1]
            data = self.data.pop(-1)
            self.maxHeapify(1)
        else:
            data = None
        return data


    def maxHeapify(self, i):
        # 왼쪽 자식 (left child) 의 인덱스를 계산합니다.
        left = i * 2

        # 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
        right = i * 2 + 1

        smallest = i
        # 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if left < len(self.data) and self.data[smallest] < self.data[left]:
            # 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다.
            smallest = left

        # 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if right < len(self.data) and self.data[smallest] < self.data[right]:
            # 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다.
            smallest = right

        if smallest != i:
            # 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
            self.data[i], self.data[smallest] = self.data[smallest], self.data[i]

            # 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
            self.maxHeapify(smallest)


def solution(x):
    return 0

GitHub

https://github.com/ds02168/Study_Algorithm/blob/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/%EC%96%B4%EC%84%9C%EC%99%80%20%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80%20%EC%B2%98%EC%9D%8C%EC%9D%B4%EC%A7%80/22%2C23%EA%B0%95/22%2C23%EA%B0%95.py