지금 정리하려는 힙은 메모리에서의 힙이 아니라, 자료구조 힙이다.

OS에 힙 메모리 공간을 만들어낸 사람이나, 스택 메모리를 만든 사람이나 싸이코 같다. 스택은 그 활용에 있어 매우 유사한 부분이 있어, 이해는 되지만, 힙은 대체 메모리 힙과 자료구조 힙이 1도 연관이 없는데 대체 왜 이딴식으로 이름을 붙였는지 이해할 수가 없다.

아마 메모리와 자료구조의 연관성을 찾으려고 끙끙거릴 컴공과 학생들을 상상하며 짜릿함을 느끼는 싸이코패스일 것이 분명하다.

힙

힙 자료구조

힙 자료구조는 최대값이나 최소값을 찾는데 최적화 되어 있는 완전이진트리이다.

항상 최대값이나 최소값이 루트 노드에 존재하도록 만들어져있어, 배열로 만들어졌을 때, 항상 인덱스 0에 최대값이나 최소값이 존재한다.

일반적으로 정렬을 하거나, 우선순위 큐를 구현하는데 사용된다.

위의 그림과 같이 최소힙의 경우 하위 노드보단 상위 노드는 반드시 작게 구성되어있고, 자식 노드의 왼쪽과 오른쪽의 크기는 상관이 없다.

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

힙에서 자료의 삽입은 약간 독특하게 이루어진다. 반드시 완전이진트리의 형태를 유지해야 하기 때문에, 그 구조를 유지하기 위한 작업이 필요하다.

1. 값과 상관없이, 현재 트리에서 가장 마지막 위치에 새로운 자료를 추가한다.

2. 형제 노드의 값과 비교는 할 필요 없고, 바로 부모 노드와 비교하여, 자신보다 작은지 확인한다. 자신보다 크다면, 교체해야 한다.

3. 힙의 정의에 부합할 때 까지 교체한다. 이 과정에서 O(logN) 의 시간복잡도가 소요된다.

힙에서 자료 삭제

힙에서 자료의 삭제는 반드시 루트 노드에서만 이루어진다. 루트 노드에는 최소값만 들어있기 때문에, 자료를 pop하게 되면 반드시 최소값만 나오게 된다.

그러면 다시 힙구조를 재구성해주어야 하는데, 중요한 것은 완전이진트리의 형태를 유지해야 한다는 것. 이를 위해서는 완전 이진트리의 가장 마지막 값을 헤드로 옮긴 후 힙 재구성을 해주어야 한다.

1. 루트 노드 제거

2. 가장 마지막 노드를 헤드 노드로 이동

3. 헤드 노드가 하위 노드보다 크다면, 두 노드 중 작은 노드와 교환 -> 부모 노드는 반드시 하위 노드보다 작아야 하기 때문에, 하위 노드 중 하나를 선택해야 되는 경우 최소의 값을 선택해야 함. 이 과정을 거치면 다시 힙구조가 완성되는데 O(logN)이 소요된다.

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

    def push(self, val):
        index = len(self.arr) - 1
        self.arr.append(val)

        while (index - 1) // 2 >= 0:
            if self.arr[(index - 1) // 2] > self.arr[index]:
                self.arr[(index - 1) // 2], self.arr[index] = self.arr[index], self.arr[(index - 1) // 2]
                index = (index - 1) // 2
            else:
                break

    def pop(self):
        if not self.is_empty():
            return False

        ans = self.arr[0]
        self.arr[0] = self.arr[-1]
        self.arr.pop()

        index = 0
        length = len(self.arr)
        while index * 2 + 2 < len(self.arr):
            left = index * 2 + 1
            right = index * 2 + 2
            if left < length and right < length:
                if self.arr[index] <= self.arr[left] and self.arr[index] <= self.arr[right]:
                    break

                elif self.arr[index] > self.arr[left] and self.arr[index] <= self.arr[right]:
                    self.arr[index], self.arr[left] = self.arr[left], self.arr[index]
                    index = left

                elif self.arr[index] <= self.arr[left] and self.arr[index] > self.arr[right]:
                    self.arr[index], self.arr[right] = self.arr[right], self.arr[index]
                    index = right

                elif self.arr[index] > self.arr[left] and self.arr[index] > self.arr[right]:
                    if self.arr[left] > self.arr[right]:
                        self.arr[index], self.arr[right] = self.arr[right], self.arr[index]
                        index = right
                    else:
                        self.arr[index], self.arr[left] = self.arr[left], self.arr[index]
                        index = left

        return ans

    def peek(self):
        if not self.is_empty():
            print(self.arr[0])
        else:
            print("no value")

    def is_empty(self):
        if not self.arr:
            return False
        else:
            return True