우선순위 큐

우선순위 큐

---

우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 예를 들어 어러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우에 우선순위 큐를 이용할 수 있다. 우선순위 값을 표현할 때는 일반적으로 정수형 자료형의 변수가 사용된다.

 

예를 들어, 물건 정보가 있고, 이 물건 정보는 물건의 가치와 물건의 무게로만 구성된다고 가정해보자. 그러면 모든 물건 데이터를 (가치, 물건)으로 묶어서 우선순위 큐 자료구조에 넣을 수 있다. 이후에 우선순위 큐에서 물건을 꺼내게 되면, 항상 가치가 높은 물건이 먼저 나오게 된다.(최대 힙 기준) 대부분의 프로그래밍 언어에서는 우선순위 큐 라이브러리에 데이터의 묶음을 넣으면, 첫 번째 원소를 기준으로 우선순위를 설정한다.

 

Python, C++, Java를 포함한 대부분의 프로그래밍 언어에서 표준 라이브러리 형태로 지원한다.

 

힙(Heap)

---

우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나이다. 최소 힙(Min Heap)과 최대 힙(Max Heap)이 있다. 최소 힙은 '값이 낮은 데이터가 먼저 삭제'되며 최대 힙은 '값이 큰 데이터가 먼저 삭제'된다. 파이썬 라이브러리에서는 기본적으로 최소 힙 구조를 이용한다.

 

우선순위 큐를 단순히 리스트를 이용해서 구현할 수도 있지만, 삭제할 때마다 모든 원소를 확인해서 우선순위가 가장 높은 것을 찾아야 하므로 최악의 경우 O(N)의 시간이 소요된다.

 

최소 힙

힙 라이브러리 사용 예제를 알아보자. 파이썬은 기본적으로 최소 힙을 제공한다.

import heapq

# 오름차순 힙 정렬(Heap Sort)
def heapsort(iterable):
  h=[]
  result=[]
  # 모든 원소를 차례대로 힙에 삽입
  for value in iterable:
    heapq.heappush(h,value)
  # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
  for i in range(len(h)):
    result.append(heapq.heappop(h))
  return result

result=heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)

 

최대 힙

파이썬에서 최대 힙은 라이브러리로 제공하지 않기 때문에 삽입, 삭제할 때 '-'를 붙인다.

import heapq

# 내림차순 힙 정렬(Heap Sort)
def heapsort(iterable):
  h=[]
  result=[]
  # 모든 원소를 차례대로 힙에 삽입
  for value in iterable:
    heapq.heappush(h,-value)
  # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
  for i in range(len(h)):
    result.append(-heapq.heappop(h))
  return result

result=heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)