[자료] Python으로 배우는 자료구조 (4) Heap

이번에는 Heap자료 구조형에 대해 정리한다.

출처 : 프로그래머스 어서와, 자료구조와 알고리즘은 처음이지?

Heap의 정의 및 기본 연산

이진트리의 한 종류로 binary heap이라고도 부른다. 

Heap에서는 Max Heap이랑 Min Heap이 있다. 두 가지가 대칭적인 개념이므로, 여기서는 Max Heap을 기준으로 설명을 풀어나가려 한다.

Max Heap의 전제 조건

- 루트 노드가 항상 최댓값을 가진다.

- 완전 이진 트리이다.

- 임의의 노드를 루트로 하는 서브트리 또한 최대 힙이다.

이러한 성질 때문에, 최대 힙의 경우는 완전히 크기 순서대로 정렬되어 있지는 않는다. 대신 완전 이진 트리를 유지해야 한다는 조건 때문에, Heap의 삽입과 삭제 연산의 시간 복잡도는 O(log n)의 형태를 가진다.

Max Heap의 구현

완전 이진트리라는 성질 때문에, 트리의 루트부터 순서대로 차 있으므로, Max Heap의 경우는 리스트를 사용하여 구분할 수 있다. 하지만 순서대로 들어와야 한다는 성질 때문에 삽입이나 삭제는 원하는 위치가 아닌 맨 끝을 기준으로 이루어진다. 리스트를 사용한 Max Heap의 기본 정의는 다음과 같다.

class MaxHeap:

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

정말 단순하게, List로 정의해버리고 끝난다!

본격적인 삽입과, 삭제를 알아보기 전에 알아두면 좋은 성질은 다음과 같다.

(1) 루트 노드는 1번 index로 정의한다.

(2) 부모노드가 a번이면, 자식 노드는 2a거나 2a+1이다.

 

Max Heap에서의 원소 삽입

우선은 삽입의 경우는 맨 마지막에 원소를 붙여야 한다. 그 후, 노드를 바꿔가며 최대 힙의 정의가 충족되도록 만들어야 한다.

(1) 맨 마지막에 삽입 후, Max Heap이 되면 그냥 끝

(2) 아닐 경우, 루트 노드에 도달하거나, 혹은 Max Heap을 만족할 때 까지 부모 노드의 값보다 자신의 값이 더 클 경우 부모와 값을 바꾸면 된다.

코드를 통해 내용을 확인하면 다음과 같다.

class MaxHeap:

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


    def insert(self, item):
        self.data.append(item) # 임시로 아이템 삽입
        pos = len(self.data) - 1 # 현재 위치 반환
        
        while pos != 1:
            if self.data[pos] > self.data[int(pos//2)]:
                self.data[pos], self.data[int(pos//2)] = self.data[int(pos//2)], self.data[pos]
                pos = pos // 2
            else:
            	break

 

Max Heap에서의 원소 삭제

삭제도 맨 마지막 노드에서만 일어나게 해야하는데, 다음과 같은 방법으로 삭제 연산을 정의 및 구현한다.

(1) 루트 노드의 데이터를 꺼내고, 맨 마지막 노드의 원소를 루트 노드의 자리에 임시로 집어 넣는다.

(2) 마지막 노드를 제거하고, 임시에 들어간 새로운 노드의 자리를 찾는다.

(3) 루트부터 출발하여, 아래로 아래로 내려간다. 더 큰 값을 가지는 노드와 자리를 바꾸면서 더 바꿀 필요가 없거나 리프 노드에 도달할 때 까지 간다.

위에서 부터 내려가기에 단순히, 자리를 바꾸는 것으로는 해결이 나지 않고 또한 자식이 2개 있을 경우 더 큰 값과 바꿔야 한다는 점도 고려해야 한다. 

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 = 2*i

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

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

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

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

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