Heap(python)

in Data Structure on 자료구조, 트리, Python, 힙

힙

  • 이진 트리의 한 종류(== binary heap)

특징

  1. 루트 노드가 언제나 최댓값 또는 최솟값을 가짐.
    • 최대 힙(max heap), 최소 힙(min heap)
  2. 완전 이진 트리
  3. 서브 트리도 모두 힙
  4. 자식 노드들 간의 위치는 상관 없음 - 느슨한 정렬
  5. 루트 노드를 1번으로 시작.
  6. 노드 번호 m을 기준으로
    • 왼쪽 자식 노드의 번호 : 2 * m
    • 오른쪽 자식 노드의 번호 : 2 * m + 1
    • 부모 노드의 번호 : m // 2

이진 탐색 트리 vs 힙

  1. 원소들은 완전히 크기 순으로 정렬되어 있는가? -> 이진 탐색 트리 : Yes, 힙 : No
  2. 특정 키 값을 가지는 원소를 빠르게 검색 가능한가? -> 이진 탐색 트리 : Yes, 힙 : No
  3. 부가의 제약 조건은 있는가? -> 힙 : 완전 이진 트리여야 한다.

최대 힙에 원소 삽입 과정

  1. 트리의 마지막 자리에 새로운 원소를 임시로 저장
  2. 부모 노드와 키 값을 비교해서 노드 위치 정렬(위로 위로 이동)

복잡도

  • 부모 노드와의 대소 비교 : O(logN)

최대 힙에서 원소의 삭제 과정

  1. 루트 노드(최댓값) 제거
  2. 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치
  3. 자식 노드들과의 값 비교를 통해 노드 위치 정렬(아래로 아래로 이동)
    • 자식 노드가 둘이 있을 때는 자식 노드 중 가장 큰 값과 비교

복잡도

  • 왼쪽, 오른쪽 자식 노드와의 대소 비교 : O(logN) - (2 * log2n)

코드 구현

  • 완전 이진 트리 구조이므로 배열을 이용해서 구현할 수 있다.
class MaxHeap:
   # 루트 노드의 시작은 1번 인덱스이므로 처음에 0번 인덱스에 None을 넣어준다.
    def __init__(self):
        self.data = [None]

   # 노드 삽입
    def insert(self, item):
        self.data.append(item)
        n = len(self.data) - 1
      #   루트 노드까지 진행
        while n > 1:
            # 부모 노드와 크기 비교
            if self.data[n] > self.data[n // 2]:
                self.data[n], self.data[n // 2] = self.data[n // 2], self.data[n]
                n //= 2
            else:
                break

   #  자식 노드와의 크기 비교를 재귀로 구현
    def maxHeapify(self, i):
        smallest = i
        left = i * 2
        right = i * 2 + 1
      #   왼쪽 노드가 존재하고, self.data[i] 노드보다 큰 경우
        if left < len(self.data) and self.data[left] > self.data[smallest]:
            smallest = left
      #  오른쪽 노드가 존재하고, self.data[i] 노드보다 큰 경우 또는 self.data[left] 노드보다 큰 경우
        if right < len(self.data) and self.data[right] > self.data[smallest]:
            smallest = right
      # 자식 노드들 중 현재 노드보다 큰 경우 재귀 호출
        if smallest != i:
            self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
            return self.maxHeapify(smallest)

    def remove(self):
        if self.data[1]:
            self.data[1], self.data[-1] = self.data[-1], self.data[1]
            data = self.data.pop()
            self.maxHeapify(1)

        else:
            data = None

        return data

오류 났던 부분

  • remove() 메소드 구현 부분에서 루트 노드부터 서브 노드들의 크기 비교 과정에서
    재귀를 생각하지 못하고, 어떻게 구현할까 고민을 했다.
  • maxHeapify() 메소드 구현 부분에서 왼쪽 노드를 먼저 확인하고, 오른쪽 노드를 확인하는 과정에서
    자식 노드들의 값이 크고, 오른쪽 노드가 왼쪽 노드보다 큰 경우는 성립하지만,
    왼쪽 노드가 오른쪽 노드보다 큰 경우 왼쪽 노드의 값을 오른쪽 노드값으로 대체된다고 생각했지만, self.data[right] > self.data[smallest] 부분에서 왼쪽 노드가 큰 경우 if문이 수행되지 않는다는 것을
    알게 되었다.