[Python] heapq 모듈

heapq : 힙을 활용해 우선순위 큐를 구현할 때 사용, O(NlogN)으로 PriorityQueue보다 빠르게 동작함, 오름차순 정렬

- heappush() : 원소 삽입

- heappop() : 원소 삭제

import heapq

heap = []

heapq.heappush(heap, 4)
heapq.heappush(heap, 9)
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)

print(heap)   # [1, 3, 4, 9]

print(heapq.heappop(heap)) # 1
print(heap)   # [3, 9, 4]

<오름차순>

import heapq

def heapsort(x):
  heap = []
  result = []
  
  for value in x:
    heapq.heappush(heap, value)
  
  for i in range(len(heap)):
    result.append(heapq.heappop(heap))
    
  return result
  
arr = [8, 1, 6, 3, 9, 2, 7, 5, 4]

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

 

<내림차순>

import heapq

def heapsort(x):
  heap = []
  result = []
  
  for value in x:
    heapq.heappush(heap, -value)
  
  for i in range(len(heap)):
    result.append(-heapq.heappop(heap))
    
  return result
  
arr = [8, 1, 6, 3, 9, 2, 7, 5, 4]

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