배열을 이용한 힙 자료구조 구현하기

06 Nov 2023

javascript

힙(Heap)은 특정한 규칙을 가지는 완전 이진 트리로, 배열을 기반으로 구현할 수 있습니다. 힙 자료구조는 우선순위 큐, 힙 정렬 등 다양한 알고리즘에서 활용되며, 효율적인 작업을 위한 데이터 구조입니다.

힙의 속성

힙은 다음과 같은 두 가지 속성을 가지고 있습니다:

완전 이진 트리 (Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 노드로 채워진 완전한 이진 트리입니다. 마지막 레벨은 왼쪽부터 순서대로 채워져야 합니다.
힙 속성 (Heap Property): 힙의 모든 부모 노드가 자식 노드보다 작은(혹은 큰) 값을 갖는 속성입니다. 이러한 속성에 따라 힙에서는 최댓값(최대 힙) 또는 최솟값(최소 힙)을 상수 시간(O(1))에 얻을 수 있습니다.

배열을 이용한 힙 구현

이제 배열을 이용하여 힙 자료구조를 구현해보겠습니다. 다음은 최대 힙(Max Heap)을 위한 배열 기반 힙 구현의 예시 코드입니다. (Python 언어를 기준으로 작성되었습니다.)

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

    def parent(self, index):
        return (index - 1) // 2

    def left_child(self, index):
        return 2 * index + 1

    def right_child(self, index):
        return 2 * index + 2

    def insert(self, item):
        self.heap.append(item)
        self._shift_up(len(self.heap) - 1)

    def _shift_up(self, index):
        while index > 0 and self.heap[index] > self.heap[self.parent(index)]:
            self.heap[index], self.heap[self.parent(index)] = self.heap[self.parent(index)], self.heap[index]
            index = self.parent(index)

    def extract_max(self):
        if len(self.heap) == 0:
            return None
        max_value = self.heap[0]
        self.heap[0] = self.heap[len(self.heap) - 1]
        self.heap.pop()
        self._shift_down(0)
        return max_value

    def _shift_down(self, index):
        max_index = index
        left_child_index = self.left_child(index)
        right_child_index = self.right_child(index)
        if left_child_index < len(self.heap) and self.heap[left_child_index] > self.heap[max_index]:
            max_index = left_child_index
        if right_child_index < len(self.heap) and self.heap[right_child_index] > self.heap[max_index]:
            max_index = right_child_index
        if index != max_index:
            self.heap[index], self.heap[max_index] = self.heap[max_index], self.heap[index]
            self._shift_down(max_index)

위의 예시 코드는 MaxHeap 클래스를 정의하고, 힙에 삽입(insert)과 최댓값 추출(extract_max)을 위한 메소드들을 구현한 것입니다. _shift_up과 _shift_down 메소드는 힙의 속성을 유지하기 위한 재귀적인 연산을 수행합니다.

마무리

이제 배열을 이용하여 힙 자료구조를 구현하는 방법에 대해 알아보았습니다. 힙은 다양한 응용 프로그램에서 유용하게 사용될 수 있으며, 효율적인 데이터 정렬 및 검색에 활용될 수 있습니다.

더 자세한 내용은 다음 참고 자료들을 참조해주세요:

#자료구조 #힙 #배열