[파이썬] heapq

heapq 라이브러리는 힙(Heap) 기능을 다룰 수 있도록 해준다. 파이썬에서의 힙은 최소 힙(Min Heap)으로 구성되어 있으며,

 

원소를 Heap에 모두 삽입했다가 빼는 것만으로도 시간 복잡도 O(NlogN)에 정렬을 수행할 수 있다.

 

기본적으로 Heap에 원소를 삽입할 때 사용하는 메서드는 heapq.heappush( ) 이고

 

Heap에서 원소를 빼낼 때 사용하는 메서드는 heapq.heappop( ) 이다. 

 

아래는 heapq를 통해 원소들을 오름차순으로 정렬한 예제이다.

 

[오름차순 예제]

import heapq

def heapsort(i):
  number = []
  result = []
  for value in i:
    heapq.heappush(number, value)
  for i in range(len(number)):
    result.append(heapq.heappop(number))
  return result

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

 

또한, 아래의 예제는 내림차순 정렬을 위해 위 코드에서 조금 수정하였다.

 

[내림차순 예제]

import heapq

def heapsort(i):
  number = []
  result = []
  for value in i:
    heapq.heappush(number, -value)
  for i in range(len(number)):
    result.append(-heapq.heappop(number))
  return result

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

 

내림차순을 수행하기 위해 heappush( )메서드 내 두번째 인자 값에 -(마이너스) 부호를 붙여주고

 

heappop( ) 메서드 인자 값에도 -(마이너스) 부호를 붙여준다.