[기본개념] Heap 구조

Heap는 BST와 매우 유사하게 생겼다

BST가 좌우 기준 대소관계를 정렬했다면, Heaps는 부모 자식 간 대소관계를 정렬했다는 특징이 있다.

(Each node has a number that is higher than all of its decendants. So the highest value is always at the top)

 

특징 3가지!

1. Complete tree 이다 (filled from left to right with NO GAPS)

2. you can have DUPLICATES! (부모 자식 간 값이 중복 가능하다)

(맨 위에 최대/ 최소값이 오느냐에 따라 Max heap, Min heap이 있다.)

3. 맨 위가 최대값이라는 거 빼면 좌우 관련 규칙이 없다. 

 

따라서, Heap is not good for seraching ! but Good for keep track of largest item at the top and quickly remove it

검색에는 최악인데, 최대/최소값 저장과 삭제에는 매우 유용하다

 

 

삽입/삭제의 시간복잡도가 O(nlogn)으로 매우 효율적이다

 

 

| 기본 구조

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

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

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

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

    def _swap(self, index1, index2):
        self.heap[index1], self.heap[index2] = self.heap[index2], self.heap[index1]

 

리스트 형식으로 만들거다. heap은 complete tree니까, 빈 칸 없이 꽉 찬 리스트랑 같음.

 

 

| Insert  (Bubble up)

    def insert(self, value):
        self.heap.append(value)
        current = len(self.heap) - 1
        while current > 0 and self.heap[current] > self.heap[self._parent(current)]:
            self._swap(current, self._parent(current))
            current = self._parent(current)

 

부모노드와 비교해서 값을 교환하여 올바르게 정렬이 될 때 까지 올라가는 것을 bubbleUp이라 한다

반대로, 부모노드와 비교해서 값을 교환하여 올바르게 정렬이 될 때 까지 내려가는 것을 bubbleDown이라 한다

 

bubble up 하는 루프가 계속 도는 조건 2가지를 잘 기억하자.

첫번째는, 해당 노드가 루트까지 올라가기 전까지 (인덱스 = 0) , 두번째는  자식노드가 부모노드보다 클 때

 

 

 

| Remove  (맨 위에 애를 삭제)

    def remove(self):
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        else:
            max_value = self.heap[0]
            self.heap[0] = self.heap.pop()  #맨 끝애를 head로 넣는다
            self._sink_down(0)      #head를 bubble down 시킨다
            return max_value

 

갱장히 복잡해보일 수 있다

삭제하고 나면, 맨 밑에거를 그 자리에 올리고 나서, 그 친구랑 자식들이랑 대소비교를 시작해야겠지

 

그러면 helper 함수가 필요하다

- 기본 함수 : 삭제한다, 맨 밑에 애를 꽂아넣는다 (삭제하는 경우도 나뉘는데, 1. 빈 리스트일때, 2. 1개밖에 없을 때, 3. 그 이상)

- helper 함수 :  아래 애랑 비교해나가면서, 대소 관계에 따라 자리를 계속 스왑한다

 

 

 

| Sink Down (Remove helper function) **

    def _sink_down(self, index):
        max_index = index
        while True:
            left_index = self._left_child(index)
            right_index = self._right_child(index)
            if left_index < len(self.heap) and self.heap[left_index] > self.heap[max_index]:
                max_index = left_index
            if right_index < len(self.heap) and self.heap[right_index] > self.heap[max_index]:
                max_index = right_index
            if index != max_index:
                self._swap(index, max_index)
                index = max_index
            else:
                return

 

조금 더 복잡할 수 있다. 근데 까보면 단순하다. 

 

부모 노드 & 왼쪽 자식 & 오른쪽 자식 3개 노드를 다 비교해서 가장 큰 애를 위로 올려야 되는거다!

세 개의  노드를 다 가리키는 인덱스를 각각 저장해줘야겠지

 

 그러니까,

맨 위의 애가 index & max index이고, 대소비교를 하면서 그 왼쪽/ 오른쪽 자식노드가 max_index로 지정된다.

index 랑 max_index가 다를 경우, 부모보다 자식이 크다는 거니까 그 두값을 바꾼다.

그리고 바뀐 애를 다시 index로 설정해주고, 거기서부터 다시 시작한다 (index = max_index)

index 를 기준으로, 왼쪽 오른쪽 애를 지정해주는거고

max_index 를 기준으로, 값을 바꿔주는거다!

 

| Min heap Insert

def insert(self, value):
        self.heap.append(value)
        current = len(self.heap) - 1
        while current > 0 and self.heap[current] < self.heap[self._parent(current)]:
            self._swap(current, self._parent(current))
            current = self._parent(current)

Max heap이랑 똑같고, 그냥 대소관계만 바꿔주면 됨

 

 

 

| Min heap Remove & Sink Down

똑같아!

def remove(self):
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        min_value = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._sink_down(0)
        return min_value
        
        
def _sink_down(self, index):
        min_index = index
        while True:
            left_index = self._left_child(min_index)
            right_index = self._right_child(min_index)
            if left_index < len(self.heap) and self.heap[left_index] < self.heap[min_index]:
                min_index = left_index
            if right_index < len(self.heap) and self.heap[right_index] < self.heap[min_index]:
                min_index = right_index
            if min_index != index:
                self._swap(min_index, index)
                index = min_index
            else:
                return