자료구조)Heap & Priority Queue

Heap은 최소값이나 최댓값을 알게 쉽게 하는 완전이진트리 입니다. 

완전 이진트리란 왼쪽부터 차례대로 넣어지는 이진트리입니다. (그렇기 때문에 BST처럼 노드 균형에 대해서 신경쓸 필요가 없습니다)

Heap은 앞서 얘기한 것처럼 최소값과 최댓값을 더 쉽게 알기 위해 고안되었습니다.

그래서 만약 최대값을 알고 싶은 최대 힙(max heap)이라면 head 위치(맨 처음위치)에 최대값이 위치하게 됩니다. 

 

이런 구조를 만들기 위해서, 새로운 값이 힙에 들어오게 되었을때 완전이진트리 구조에 의해 맨 마지막 위치에 새로운 값이 위치하게 되는데, 부모 노드와 비교해서 자식 노드가 더 크다면 계속 자리를 바꾸게 됩니다.(swap)

이런 구조에 의해 부모와 자식노드를 비교했을 때 크기 gap이 규칙으로 있지, BST처럼 왼쪽자식노드, 오른쪽 자식 노드의 크기차이가 있어야 한다는 규칙은 없습니다. 

힙에서 삭제를 한다는 것은 최댓값/ 최솟값을 빼내는 것입니다. 이때 비어진 head에 맨 마지막 요소로 넣어두고, 이 요소와 크기 차이를 비교해 swap 합니다.

이런 구조를 가지는 Heap은 삽입과 삭제에 O(logN)의 시간이 걸리게 됩니다.

 

완전이진트리를 갖는 것, 새로운 요소가 힙의 맨 마지막에 위치하는 것 때문에 힙은 트리지만 링크드리스트로 구현하지 않고 array로 구현하게 됩니다. 

부모 노드의 인덱스는 (현재 노드 / 2) , 왼쪽 자식 노드는 (부모노드*2), 오른쪽 자식 노드는 (부모노드 *2 +1)로 위치를 쉽게 알 수 있습니다. (연산의 편의성을 위해 0번째 인덱스는 None 합니다.)

이제 한번 구현해 볼까요?

class MaxHeap :
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)

    # 새로운 요소가 들어왔을때, 부모노드랑 비교해서 위로 올리는 것 
    def move_up_judge(self,inserted_index):
        #루트노드 일때는 그냥 return False
        if inserted_index <= 1:
            return False
        parnet_index = inserted_index //2
        if self.heap_array[inserted_index]>self.heap_array[parend_index]:
            return True
        else: return False
    
    def inert(self, data):
        #방어코드, 초기화 코드
        if len(self.hap_array) == 0:
            self.heap_array = list()
            self.heap_array.append(None)
            self.heap_array.append(data)
        else:
            self.heap_array.append(data)
            inserted_index = len(self.heap_array)-1 # None이 들어가기 때문
            while self.move_up_judge(inserted_index):
                parent_index = inserted_index //2
                self.heap_array[inserted_index], self.heap_array[parent_index] = self.heap_array[parent_index], self.heap_array[inserted_index]
                inserted_index = parent_index

    def move_down_judge(self, pop_index):
        left_child_index = pop_index *2
        right_child_index = pop_index*2+1

        # 왼쪽 자식 노드가 없을때 : 헤드밖에 없는 상태
        if len(self.heap_array) <= left_child_index :
            return False
        #오른쪽 자식노드가 없을때 : 왼쪽 자식 노드까지 있을때
        elif len(self.heap_array) <= right_child_index:
            if self.heap_array[pop_index] < self.heap_array[left_child_index]:
                True
            else:
                False
        # 왼쪽 오른쪽 자식노드 모두 있을때 
        else
            if self.heap_array[left_child_index] > self.heap_array[right_child_index] :
                if self.heap_array[pop_index]<self.heap_array[left_child_index]
                    return True
                else : return False
            else 
                if self.heap_array[pop_index]<self.heap_array[right_child_index]
                    return True
                else : return False

    def pop(self):
        if len(self.heap_array) <= 1:
            return None
        else:
            pop_item = self.heap_array[1]
            self.heap_array[1] = self.heap_array[-1]
            del self.heap_array[-1]
            pop_index = 1

            while self.move_down(pop_index):
                left_child_index = pop_index *2
                right_child_index = pop_index *2 +1

            # case2: 오른쪽 자식 노드만 없을 때
            if right_child_popped_idx >= len(self.heap_array):
                if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                    self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
                    popped_idx = left_child_popped_idx
            # case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
            else:
                if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]:
                    if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                        self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
                        popped_idx = left_child_popped_idx
                else:
                    if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
                        self.heap_array[popped_idx], self.heap_array[right_child_popped_idx] = self.heap_array[right_child_popped_idx], self.heap_array[popped_idx]
                        popped_idx = right_child_popped_idx
        
        return pop_item

생각보다 복잡하죠?

파이썬에는 다행이도 heap 라이브러리가 있답니다.(파이썬 최고🥰)

파이썬은 기본적으로 Min Heap 이에요, 그래서 제일 작은 수가 가장 위에 옵니다. 

만약 MaxHeap을 쓰고 싶다면 입력 시 데이터에 -(마이너스)를 붙여서 넣어주면 됩니다.

import heapq

heap_array = []

#데이터를 넣을 때 
heapq.heappush(heap_array, 1)

#데이터를 뽑을 때 : 최소값을 뽑을 때
heapq.heappop(heap_array)

#최소값을 뽑지 않고 보고만 싶을때 - 기본적으로 heap_array는 list이다.
print(heap_array[0])

#기존의 리스트를 heap형태로 변환하고 싶을때
before = [6,3,7,2,1]
heapfy(before)

제목에 Priority Queue가 있는데, Priority Queue의 작동방식이 큐와 거의 동일합니다. 

그래서 PriorityQueue를 구현하고 싶을때 Queue로 구현해주면 됩니다. 

이때, 데이터를 넣을 때 (우선순위, 넣을 데이터) 이렇게 튜플 형태로 집어 넣으면 됩니다. 

 

-------

힙도 끝~~ 자료구조가 어느정도 끝나서 머릿속에 들어오니 세상을 보는 것이 명쾌해진 기분이네요~~