자료구조와 알고리즘 - 우선순위 큐(Priority Queue)와 힙 정렬(Heap Sort)

 

---

- 우선순위 큐:

 큐(Queue)로 이루어진 자료에서 우선순위가 높은 데이터가 먼저 pop되는 것을 말한다. 이때 우선순위가 높다는 것은 데이터 중에서 가장 높은 값, 가장 낮은값 등 기준은 활용하는 것에 따라 다르다.

 

힙에서 배웠듯이 힙구조(최대 힙이라고 한다면)는 루트노드에 가장 높은 데이터의 값을 배치한다.

 

pop을 한 후에도(루트노드 값을 pop) 다시 최대힙구조를 만족시키기 위한 작업을 한다.

 

즉, 남은 데이터 값 중에서 가장 높은 값을 다시 루트노드에 배치하게 된다.

 

이는 우선순위 큐의 정의대로, 우선순위가 높은 값이 먼저 pop되는 것을 구현 하게 되는 것이다.

 

 

-힙 정렬:

 힙 정렬이란 힙구조를 이용한 정렬을 말한다. 우선 순위 큐는 힙을 이용하여 구현하기 때문에 우선순위 큐를 이용하여 힙정렬을 수행할 수 있다.

 

 

import pickle
import time
from Heap_array import maxheap

with open("./list_data.pickle", "rb") as f:
    lst = pickle.load(f)
    
start = time.time()

##무작위로 배열된 리스트를 heap에 넣는다.
heap = maxheap(lst[0])
for i in lst[1:]:
    heap.add_(i)

###pop해서 나온 값을 다른 리스트에 저장한다.
sorted_lst = []
for _ in range(len(heap.array)-1):
    b = heap.pop_()
    sorted_lst.append(b)

end = time.time()
print("힙정렬의 걸린 시간: {}".format(end-start))

위 코드는 힙을 직접 구현했던 파일을 import해서 수행하였다.(https://kokoko12334.tistory.com/10)

 

1.먼저 데이터의 값이 무작위로 배열된 리스트를 maxheap에 하나 씩 넣는다.

 

2. 힙구조에 있는 데이터를 하나씩 popleft(왼쪽부터 뺌)를 한다. 이때 최대힙이므로 pop된 값들은 항상

최대 값이다.(남아 있는 maxheap중에서)

 

3. pop된 값을 다른 리스트에 넣는다. 최종 결과로 내림차순으로 정렬된 배열을 얻을 수 있다.

 

 

 

힙정렬의 시간 복잡도는 

힙구조를 만드는 과정 (log(n))과 pop하는 과정(n)을 합친 O(nlog(n))이다.

 

 

 

선택정렬(시간복잡도=O(n^2))과 비교하여 빠른 성능을 보여준다.(같은 무작위 리스트로 비교하였다.)

 

 

 

 

-파이썬 내장모듈을 이용하여 우선순위 큐 구현하기

 파이썬에서는 heap구현할 수 있는 라이브러리가  PriorityQueue, heapq 2개 있다.(둘 다 최소 힙)

 

1. PriorityQueue()

 

from queue import PriorityQueue

que = PriorityQueue()
lst = [29,20,10,15,1,6,8,21]

for i in lst:
    que.put(i)  #우선순위큐에 넣기


#pop하기
que.get()

PriorityQueue()는 객체를 만들고 메소드를 이용한다.

 

 

2. heapq

 

from heapq import *

lst = [29,20,10,15,1,6,8,21]

heap_ = []   #힙구조를 담을 리스트를 따로 만든다.

for i in lst:
    heappush(heap_, i)

#pop
heappop(heap_)

heapq는 힙을 담을 리스트를 따로 만든 다음에, 함수처럼 이용한다.

 

heapq와 PriorityQueue()에 대한 내용을 찾아보면 PriorityQueue()는 쓰레드 세이프를 위한 과정을 추가적으로 수행하기 때

 

문에 heapq가 PriorityQueue()보다 빠르다고 한다.(내부코드를 보면  PriorityQueue()는 heapq를 사용하고 있다.)  

 

 

 

-heapq의 그 외 기능 및 활용

 

1)최대힙 구현방법

 heappush(빈 배열, (우선순위, 값))을 이용하여 최대힙 구현이 가능하다.

 

예를 들어 (1,"b"), (2, "a"), (3,"c")는 우선순위에 따라 b,a,c로 정렬된다.(최소힙이므로 숫자가 작을수록 우선순위가 높음)

 

# 최소힙이므로 1234 에서 우선순위가 높은 값은 1이다.
# 이때 -1 -2 -3 -4 를 해준다면 즉, 부호를 바꾸면 이때 우선순위가 높은값은 -4가 된다.

lst = [29,20,10,15,1,6,8,21]
heap_ = []
for i in lst:
    heappush(heap_,(-i,i))
print(heap_)

 

 

2)heapify

  배열을 힙구조로 한번에 바꾸어준다.

lst = [29,20,10,15,1,6,8,21]
heapify(lst)
print(lst)

 

사용하다 보면 같은 배열을 넣는데도 heapify랑 heappush랑 힙배열의 결과가 다르게 나올때도 있다.

 

그 이유는 heapify는 기존 배열의 순서대로 일단 힙에 넣는다.(아직 힙구조를 만족하지는 않음)

그 다음에서야 힙구조를 만족할때 까지 연산을 시작한다.(부모노드 값< 자식노드 값)

 

heappush는 for문을 써서 배열의 값을 하나 하나씩 넣으면서 힙구조를 만들어 나간다.

 

결론은 둘 다 최종적으로 힙구조를 만들기 때문에 문제는 없다. 

 

 

3)nsmallest, nlargest

 각각 1~n번째로 작은 값, 큰 값을 return한다.

lst = [29,20,10,15,1,6,8,21]

nsmallest(3, lst)
nlargest(3, lst)