heapq 라이브러리 문법

📌heapq

다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 우선순위 큐 기능을 구현하고자 할 때 사용

파이썬의 힙은 최소 힙으로 구성(최소힙: 최상단 원소가 항상 가장 작은 원소)

단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN)에 오름차순 정렬이 완료

 

📌heapq 메서드

heapq.heappush(): 힙에 원소 삽입

heapq.heappop(): 힙에서 원소 꺼냄

 

📌힙 정렬을 heapq로 구현하는 코드

import heapq


def heapsort(iterable):
    h = []  # 힙
    result = []  # 결과 리스트
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 리스트에 꺼내어 담기
    for _ 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)

 

 

📌참고

https://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬