[자료구조] 힙 (Heap)

728x90

본 포스트는 필자가 합습하고 작성한 글이기 때문에 틀린 내용이 있을 수 있습니다.
참고 : https://maneeshaindrachapa.medium.com/heap-data-structure-in-golang-98641a32d2e3

힙 (Heap) 개요

힙은 완전 이진 트리 (Complete Binary Tree)의 일종으로 주로 우선순위 큐 (Priority Queue)를 구현하는데 사용

종류

최대 힙 (Max Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 같은 트리
최소 힙 (Min Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 항삭 작거나 같은 트리

장점

루트 노드에서 쉽게 가장 높은(최대 힙) 또는 가장 작은(최소 힙) 원소에 접근 가능하다.
동적으로 크기가 조절되는 자료구조다. 초기 크기를 미리 지정할 필요가 없다.
배열을 사용해 구현할 수 있으며, 포인터를 사용하는 다른 트리 구조와 달리 추가적인 메모리를 필요로 하지 않는다.

단점

정렬된 구조가 아니기 때문에 전체 원소를 정렬된 순서로 접근하려면 추가적인 연산이 필요하다.
배열이나 연결 리스트와 비교하면 힙의 구현과 조작이 좀 더 복잡하다. 힙의 속성을 유지해야 하기 때문.

주요 연산

push : 새로운 노드를 힙에 추가
pop : (최대 힙의 경우) 최댓값 또는 (최소 힙의 경우) 최솟값을 리턴하고 제거
peek : (최대 힙의 경우) 최댓값 또는 (최소 힙의 경우) 최솟값을 리턴
heapify : 배열을 힙 구조로 변환

시간 복잡도

push : O(log n)
pop : O(log n)
peek : O(1)
heapify : O(n)

공간 복잡도

모든 경우 : O(n)

구현

힙은 일반적으로 배열을 기반으로 구현, 배열의 각 요소가 트리의 노드와 일치한다.

만약 부모 노드의 인덱스가 i 라면

왼쪽 자식의 인덱스 : 2i + 1
오른쪽 자식의 인덱스 : 2i + 2

이런 방식으로 힙을 배열로 표현 할 수 있음

힙에서 자료 삽입 (최소힙의 경우)

완전 이진 트리의 형태를 유지해야 하기 때문에, 그 구조를 유지하기 위한 작업이 필요

값과 상관없이, 현재 트리에서 가장 마지막 위치에 새로운 자료를 추가
부모 노드와 비교하여 자신보다 작은지 확인, 크다면 교체
힙의 정의에 부합할 때 까지 교체, 이 과정에서 O(log n)의 시간 복잡도가 소요

힙에서 자료 삭제

자료의 삭제는 반드시 루트 노드에서만 이루어짐

루트 노드에는 최솟값만 들어있기 때문에 자료를 pop하면 반드시 최솟값만 나옴

루트 노드 제거
가장 마지막 노드를 헤드 노드로 이동
헤드 노드가 하위 노드보다 크다면, 두 노드 중 작은 노드와 교환
→ 부모 노드는 반드시 하위 노드보다 작아야 하기 때문에, 하위 노드 중 하나를 선택해야 하는 경우 최소의 값을 선택

리스트 기반 힙

class MinHeap:
    def __init__(self):
        self.heap = []

    def push(self, val):
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)

    def pop(self):
        if not self.heap:
            return None
        self._swap(0, len(self.heap) - 1)
        root = self.heap.pop()
        self._sift_down(0)
        return root

    def peek(self):
        return self.heap[0] if self.heap else None

    def heapify(self, arr):
        self.heap = arr
        for i in reversed(range(len(self.heap) // 2)):
            self._sift_down(i)

    def _parent(self, idx):
        return (idx - 1) // 2

    def _left_child(self, idx):
        return 2 * idx + 1

    def _right_child(self, idx):
        return 2 * idx + 2

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def _sift_up(self, idx):
        parent = self._parent(idx)
        while idx > 0 and self.heap[parent] > self.heap[idx]:
            self._swap(parent, idx)
            idx = parent
            parent = self._parent(idx)

    def _sift_down(self, idx):
        left = self._left_child(idx)
        right = self._right_child(idx)
        smallest = idx

        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right
        if smallest != idx:
            self._swap(idx, smallest)
            self._sift_down(smallest)