[자료구조] 우선순위 큐, 힙

💡 우선순위 큐?

일반적인 큐는 First-In-First-Out구조이지만,

우선순위 큐(Priority Queue)는 우선순위가 높은 데이터가 먼저나오는 구조이다.

우선순위 큐를 배열이나 연결리스트로 구현할 시에는 우선순위에 맞게 데이터를 삽입하는 시간이 오래걸리게 된다.

때문에 우선순위 큐는 힙을 이용해서 구현한다.

---

💡 힙?

힙은 최대값과 최소값을 빠르게 찾기 위해 고안된 완전이진트리이다.

(=변형된 트리의 형태)

 

[ 힙의 구조 ]

: 최대값을 구하기 위한 구조인 최대힙과 최소값을 구하기 위한 구조인 최소힙이 있다.

힙은 다음과 같이 두가지 조건을 가지고 있는 자료구조이다. (최대힙 기준)

1) 부모노드는 자식노드의 값보다 크거나 같다.

2) 완전 이진 트리형태

 

최소힙과 최대힙

 

[ 힙과 이진 탐색 트리 비교 ]

* 공통점 : 이진트리다.

* 차이점 :

- 힙은 각 노드의 값이 자식노드보다 크거나 같다.

- 이진 탐색 트리는 왼쪽 자식노드의 값이 가장 작고, 부모노드, 오른쪽 자식노드 순이다.

- 힙은 왼쪽 자식이 클지 오른쪽 자식이 클지는 모른다.

* 목적 : 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조다.

 

 

💡 힙의 동작

[ 데이터 삽입 ]

1. 완전 이진트리로 만든다.

: 부모노드보다 크더라도 일단은, 완전 이진트리로 만들고 시작한다. 그래서 왼쪽 최하단부 노드부터 채운다.

2.  자식노드가 부모노드보다 크다면 바꿔준다.

: 20과 8을 바꾸고, 20과 15와 바꿔준다. 루트 노드가 될때까지 조건을 체크해준다.

[ 데이터 삭제 ]

1. 루트 노드를 삭제한다.(=최대값을 뽑아낸다)

2. 최하단부의 노드를 루트로 설정한다.

 3. 자식노드가 부모보다 크다면, 자식노드 둘 중 더 큰 값과 바꾼다.

: 15가 10보다 크기 때문에 15와 8을 바꾼다. 자식노드가 없을때까지 이를 반복한다.

💡 힙의 구현(with Python)

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None) # 1부터 시작할 예정
        self.heap_array.append(data)

    # 루트노드가 자식노드랑 위치를 변경해야하는가를 판단
    def move_down(self, popped_idx):
        left_child_popped_idx = popped_idx * 2
        right_child_popped_idx = popped_idx * 2 + 1

        # case1: 왼쪽 자식 노드도 없을 때
        if left_child_popped_idx >= len(self.heap_array):
            return False
        # case2: 오른쪽 자식 노드만 없을 때 (완전이진트리라는 것을 유의하자)
        elif right_child_popped_idx >= len(self.heap_array):
            if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                return True # 자식노드가 더 크니까 바꿔줘야함
            else:
                return False
        # 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]:
                    return True # 자식노드가 더 크다면 바꿔줘야함
                else:
                    return False
            else:
                if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
                    return True # 자식노드가 더 크다면 바꿔줘야함
                else:
                    return False

    def pop(self):
        if len(self.heap_array) <= 1:
            return None

        returned_data = self.heap_array[1]
        self.heap_array[1] = self.heap_array[-1] # 루트노드를 최하단 노드로 변경
        del self.heap_array[-1]
        popped_idx = 1

        while self.move_down(popped_idx):
            left_child_popped_idx = popped_idx * 2
            right_child_popped_idx = popped_idx * 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 returned_data

    # 현재 노드가 상위노드와 바꿔야하는지를 판단
    def move_up(self, inserted_idx):
        if inserted_idx <= 1: # 루트노드면 바꿀 노드가 없다.
            return False
        parent_idx = inserted_idx // 2
        if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
            return True
        else:
            return False

    def insert(self, data):
        if len(self.heap_array) == 1: # 방어코드
            self.heap_array.append(data)
            return True

        self.heap_array.append(data) # 일단 완전 이진트리로 만든다
        inserted_idx = len(self.heap_array) - 1

        while self.move_up(inserted_idx): # 현재노드를 상위노드와 바꿔야한다고 판단했다면
            parent_idx = inserted_idx // 2
            self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
            inserted_idx = parent_idx
        return True

heap = Heap(15)
heap.insert(10)
heap.insert(20)
heap.insert(11)

print(heap.heap_array) # 확인 [None,20,15,11,10]
print(heap.pop()) # 20
print(heap.heap_array) # 확인 [None,15,11,10]

 

 

💡 힙의 시간복잡도

우선 최대 노드의 개수가 N이라면, 트리의 높이 h = \( log_{2}(N+1)-1 \)이다.

삽입 삭제시, 최악의 경우에는 root노드에서 leaf 노드까지 비교해야함으로 O(logn)의 시간 복잡도를 가진다.

단순 배열에서 최대/최소값을 찾으려면 O(n)의 시간복잡도를 가지는 것에 비하면 훨씬 빠른 속도로 최대/최소값을 찾을 수 있다.

 

💡 파이썬에서 힙 사용하기

* 최소힙

import heapq

# 최소힙
minHeap = []
heapq.heappush(minHeap, 2)
heapq.heappush(minHeap, 3)
heapq.heappush(minHeap, 1)

# 최소값 출력
while minHeap:
    print(heapq.heappop(minHeap), end=" ")

 

* 최대힙

: 파이썬 라이브러리에서는 기본적으로 최소힙만 제공하고 있다.

때문에 최소힙을 최대힙처럼 사용하기 위해서 우선순위에 해당하는 값에 음수 부호(-)를 붙여서 넣었다가, 꺼낼때에 다시 음수 부호(-)를 붙여서 원래의 값으로 돌리는 방식을 사용할 수 있다.

 

import heapq

# 최대힙
maxHeap = []
heapq.heappush(maxHeap, -2)
heapq.heappush(maxHeap, -3)
heapq.heappush(maxHeap, -1)

# 최댓값 출력
while maxHeap:
    print(-heapq.heappop(maxHeap), end=" ")

 

 

 

 

출처

스파르타 코딩클럽 알고리즘 강의

패스트캠퍼스 알고리즘 강의