까먹기 전에 적어두는 Heap(최대 힙 버전)

class BinaryMaxHeap:
    def __init__(self):
        self.items = [None]

    def insert(self, k):
        self.items.append(k)
        self._percolate_up()

    def _percolate_up(self):
        cur = len(self.items) - 1 # 계산의 편의성을 위해서 첫 자리가 1이기 때문에

        parent = cur // 2 # 자식노드는 부모노드 * 2 +1 이므로, 자식노드의 위치를 2로 나눈 몫이 부모노드의 위치가 된다.

        while parent > 0:
            if self.items[cur] > self.items[parent]: # 만약 자식이 부모보다 크다면
                self.items[cur], self.items[parent] = self.items[parent], self.items[cur] # 자식과 부모의 자리 바꾸기

            cur = parent
            parent = cur // 2

    def extract(self):
        if len(self.items)  - 1 < 1: # 길이가 1인경우(0번째 데이터가 항상 None이기 때문에) 추출할 데이터가 없으므로 None 반환
            return None

        root = self.items[1] # 추출할 데이터는 항상 힙의 가장 앞에 있으므로
        self.items[1] = self.items[-1] # 가장 뒤의 데이터를 최상단으로 옮겨준다. (추후에 규칙에 따라 힙에 재배치 하기 위해서)
        self.items.pop() # 최상단으로 옮겨진 말단 데이터를 삭제한다.
        self._percolate_down(1) # 최상단으로 옮겨진 데이터를 규칙에 따라 재배치한다. (아래의 메소드)

        return root # 요청받은 최상단값(최대값)을 반환한다.

    def _percolate_down(self, cur):
        biggest = cur # 현재의 가장 상단의 위치를 cur로 설정
        left = cur * 2 # 현재 위치의 자식 노드중 왼쪽
        right = cur * 2 + 1 # 현재 위치의 자식 노드중 오른쪽

        # 왼쪽 자식노드의 위치가 힙의 길이보다 작고(힙의 길이를 초과하면 값이 없으므로) 왼쪽 자식 노드가 오른쪽 자식 노드보다 클 경우
        if left <= len(self.items) - 1 and self.items[left] > self.items[right]:
            biggest = left # 둘중 더 큰 값을 새로운 biggest라고 한다.
        # 오른쪽 자식노드의 위치가 힙의 길이보다 작고(힙의 길이를 초과하면 값이 없으므로) 오른쪽 자식 노드가 왼쪽 자식 노드보다 클 경우
        if right <= len(self.items) - 1 and self.items[right] > self.items[left]:
            biggest = right # 둘중 더 큰 값을 새로운 biggest라고 한다.
        # 현재 cur와 비교할 필요가 없는 이유 - 말단 데이터를 최상단으로 옮겨왔기 때문에 cur는 자식노드보다 작기때문
        # 즉, 끝에 도달할 때 까지(right <= len(self.items) -1 거나 left <= len(self.items) -1때까지) 반복하면 된다.

        if biggest != cur: # biggest의 값이 변동했을 때(= 위의 조건문이 작동했을 때)
            self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur] # cur와 biggest의 자리를 바꿔준다. (더 큰 값이 위로가야하기 때문에)
            self._percolate_down(biggest) # 재귀함수로 위의 과정을 반복한다. biggest의 값이 변동이 없을때까지(= 위의 조건문이 작동하지 않았을 때, right <= len(self.items) -1 거나 left <= len(self.items) -1때)

 

최소 힙의 경우는 stack, queue와 다르게 부등호만 바꿔주면 되기때문에 굳이 주석을 달면서 분석하지는 않고 코드 구현을 연습하는 용도로 이용했다.