[내장 라이브러리] 힙큐 heapq, 정렬큐

힙큐의 사용

이진트리 내장되어 있어서 sorting 효율적으로 해주고, pop과 push로 큐로 쓰기 좋다.

import heapq
q = [1,4,5]
>>> [1,4,5]

heapq.heappop(q) # 최소값 반환 1
q
>>> [4,5]

heapq.heappush(q,5) # 순서에 맞게 삽입
q
>>> [4,5,5]

 

---

22. 9. 17. 추가

heapq.heapify({list})

heapify는 리스트를 heap으로 정렬해준다. [3,2,1] => [1,2,3]

다만 사용법이 헷갈리기 쉬운데, 할당을 따로 하는 게 아니고, sort() 메서드 쓸 때 처럼 실행만 시켜주면 된다.

import heapq as hq

Alist = []
# Case 1
hq.heapify(Alist)
print(Alist)

# Case 2
h = hq.heapify(Alist)
print(h)

Case 1 이 맞고, Case2 처럼 할당하거나, 원래 변수에 재할당하면 None 출력된다.

 

heapq.heappush({list}, {item})

heappush는 sort처럼 전부를 정렬하지 않는다. 

다만 heappop할 때 최솟값을 반환해주는 걸 약속한다.

 

배열 [0, 1, 3, 2, 5, 6, 10, 4, 3] 에서

heappop을 반복할 때, 

가장 작은 수 순서인

0 => 1 => 2 => 3 => 3 => 4 ... 순서로 출력된다.

 

 

 

" 반환 전 배열, pop으로 반환된 수, 반환된 뒤 배열 " 반복