WEEK02 - TIL 우선순위 큐(Priority Queue)

- 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다.

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

ex. 어떤 물건 데이터를 자료구조에 넣었다가 가치가 높을 물건부터 꺼내서 확인해야 하는 경우, 우선순위 큐에 각각의 물건 정보를 가치 데이터와 함께 우선순위 큐에 넣었다가 꺼낼 때

자료구조	추출되는 데이터
스택 (stack)	가장 나중에 삽입된 데이터
큐 (queue)	가장 먼저 삽입된 데이터
우선순위 큐 (priority queue)	가장 우선순위가 높은 데이터

 

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

1. 단순히 리스트를 이용해 구현

= 리스트에 차례대로 데이터를 연달아 넣고, 꺼낼 때는 리스트에서 각각의 데이터를 확인한 다음에 값이 가장 큰 데이터를 뽑아 추출

2. 힙(heap)을 이용해 구현 (아래 자세히 설명~)

 

- 데이터의 개수가 n일때, 구현 방식(리스트, 힙)에 따라 시간 복잡도는 다음 표와 같다.

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙(Heap)	O(logN)	O(logN)

리스트: 데이터를 삽입할 때 뒤에 연달아 넣으면 되기에 시간 복잡도는 1, 데이터를 삭제할 때는 우선순위가 가장 높은 데이터여야 하기 때문에 가장 높은 우선순위를 가지는 데이터를 찾기 위해 선형적인 탐색 시간을 갖게 된다.

힙: 데이터를 넣는 것과 빼는 과정에서 모두 최악의 경우에도 시간 복잡도 O(logN)을 보장하는 방식으로 동작

└→ 단순히 n개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다 (힙 정렬) = 이 경우 시간 복잡도는 O(NlogN)이다. [병합 정렬과 같은 다른 일반적으로 사용되는 정렬 알고리즘과 동일하게 빠른 정렬 알고리즘 == 힙 정렬]

 

힙(heap)의 특징

- 힙은 완전 이진 트리 자료구조의 일종이다.

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

- 힙은 두 가지로 분리할 수 있다.

-- 최소 힙 (min heap)

1. 루트 노드가 가장 작은 값을 가짐
2. 따라서 값이 작은 데이터가 우선적으로 제거

☞ 오름차순 정렬을 한다고 하면 최소힙에 n개의 데이터를 넣고 꺼내기만 해도 오름차순 정렬된 데이터가 나옴

 -- 최대 힙 (max heap)

1. 루트 노드가 가장 큰 값을 가짐
2. 따라서 값이 큰 데이터가 우선적으로 제거

* 완전 이진 트리 (Complete Binary Tree)

- 힙은 완전 이진 트리 형식을 따른다.

- 루트 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리를 의미

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

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

+ 힙에 새로운 원소가 삽입 = O(logN)의 시간 복잡도로 힙 성질을 유지하도록 한다.

이때 기본적으로 힙 자료구조는 완전 이진 트리를 따르기 때문에 균형 잡힌 트리로서 동작한다는 게 특징 == 즉, 최악의 경우에도 시간복잡도를 유지한다

+ 힙에서 원소가 제거될 때 = O(logN)의 시간 복잡도로 힙 설질을 유지하도록 한다.

원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 한다.

이후에 루트 노드에서부터 하향식으로(더 작은 자식 노드로) Heapify()를 진행한다.

 

- 우선순위 큐 라이브러리를 활용한 힙 정렬 구현 예제

import heapq #파이썬에서는 기본적으로 최소힙 형태로 동작해서 오름차순 정렬이 수행됨
import sys

input=sys.stdin.readline

def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h,value) #담기 /// 최대힙으로 동작하게 만들고 싶으면 -를 붙여야 함!!
        # heapq.heappush(h,-value) // 최대힙 예시

    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h)) # 최대힙으로 동작하게 만들고 싶으면 -를 붙여야 함!!
        # result.append(-heapq.heappop(h))
    return result

n=int(input())
arr=[]

for i in range(n):
    arr.append(int(input()))

res=heapsort(arr)

for i in range(n):
    print(res[i])

 

참고

heapq.heappush	값을 heap으로 push
heapq.heappop	heap에서 가장 작은 항목을 pop하고 반환 *힙이 비어있으면 indexError가 발생하는데, 팝하지 않고 가장 작은 항목을 찾으려면 heap[0]이용
heapq.heappushpop	값을 heap으로 push하고, heap에서 가장 작은 항목을 pop하고 반환하는 액션을 모두 한다. >> 별도로 호출하는 것보다 효율적으로 실행!

 

이론 끗~💃