[자료구조] 우선순위 큐 (Priority Queue) 와 힙 (Heap)

개인 공부 및 기록을 위해 작성하였습니다.

 

우선순위 큐와 그냥 큐

큐 (Queue) : 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료 구조

우선순위 큐 (Priority Queue) : 우선 순위가 높은 데이터가 먼저 나가는 형식의 자료 구조

우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 

 

우선 순위 큐 주요 동작

insert - 아이템의 우선순위 정보 같이 넣어주는 것

delete - 가장 우선순위가 높은 애를 빼내는 것 

peek - delete와 유사하나

우선순위 큐를 구현하는 방법

1. 단순 리스트를 이용하여 구현한다.

2. 힙(Heap)을 이용하여 구현한다. 

위의 표와 같이 리스트는 데이터를 일일히 삽입하는데 O(1)의 복잡도를 갖지만 삭제하는데에는 해당 데이터를 찾는데에 있어 리스트 내 모든 원소를 다 훑어야 함으로 O(N) 시간 복잡도가 소요된다. 

반면 힙은 삽입과 삭제 둘 다 O(logN)의 시간 복잡도가 쓰여 시간 복잡도가 크게 증가하지 않는다는 특징이 있다. 

힙

완전이진트리 형태의 자료 구조를 갖는다.

힙에서는 항상 루트 노드(root node)를 제거한다.

여러 개의 값 중 최댓값/최솟값을 찾아내는 연산이 빠르다.

최소 힙(min heap)

• 루트 노드가 가장 작은 값을 가진다.
• 따라서 값이 작은 데이터가 우선적으로 제거된다. 

-> 우측의 트리를 보면 각각의 트리마다 root 자리에 최소값이 위치해 있는 것을 확인할 수 있다.

 

 

 

최대 힙(max heap)

• 루트 노드가 가장 큰 값을 가진다.
• 따라서 값이 큰 데이터가 우선적으로 제거된다. 

-> 최대 힙은 각 트리마다 root 자리에 최댓값이 위치해 있는 모습이다.

 

 

완전 이진 트리 (Complete Binary Tree)

: 루트 (root) 노드부터 시작해서 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리를 의미한다.

위의 그래프에서 알 수 있듯, 왼쪽 자식 노드부터 채워져 있지 않은 경우, 완전 이진 트리가 아니고, 왼쪽부터 자식 노드가 잘 채워져 있으면 완전 이진트리라고 할 수 있다.

 

최소 힙 구성 함수: Min-Heapify()

파이썬은 기본적으로 min heap 자료구조를 사용한다. 

: (상향식) 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체한다.

자식노드와 부모 노드를 비교하면서 부모노드에 더 작은 숫자가 위치하게 바꿔준다.