이 포스팅은 이것이 취업을 위한 코딩테스트다 APPENDIX A 코딩테스트를 위한 파이썬 문법 파트를 읽고 공부한 내용을 정리하는 용도로 작성되었습니다.
APPENDIX A에 수록된 문법 외에 개인적으로 공부한 내용을 추가해 두었으며, 예제는 직접 연습하며 작성하였기에 교재와 다를 수 있습니다.

heapq

힙 기능을 위한 표준 라이브러리

• 다익스트라 최단 경로 알고리즘 등 우선 순위 큐 기능을 구현할 때 사용한다.
• 코딩테스트 환경에서는 heapq가 PriorityQueue 라이브러리보다 빠르게 작동한다.

heapq.heappush(): 원소 삽입
heapq.heappop(): 원소 삭제

힙 정렬(heap sort)

힙 정렬은 max heap이나 min heap 트리를 이용한 정렬 방식으로 내림차순 정렬을 위해서는 max heap이, 오름차순 정렬을 위해서는 min heap이 사용된다.

오름차순 정렬

• 파이썬에는 최소 힙(Min Heap)이 구현되어 있기 때문에 원소를 힙에 전부 삽입했다가 제거함으로써 오름차순으로 정렬 할 수 있다. O(NlogN)

1. 모든 원소를 차례대로 heap에 삽입한다.
2. 힙에 삽입된 모든 원소를 차례대로 result에 담는다.

import heapq

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

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

# result
[0, 1, 3, 5, 6, 7, 8, 9] # 오름차순 정렬

내림차순 정렬

• 파이썬에는 최대 힙(Max Heap)이 구현되어 있지 않기 때문에 내림차순 정렬을 위해서는 부호를 바꾼 뒤 최소 힙을 이용하여 정렬하고 다시 부호를 바꿔주어야 한다.

1. 모든 원소에 -를 붙인 값을 heap에 삽입한다.
2. heap의 원소를 꺼낸 뒤 다시 -를 붙여 result에 담는다.

def heapsort(iterable):
    heap = []
    result = []
    for value in iterable:
        heapq.heappush(heap, -value)
    # print(heap)
    # [-9, -8, -6, -5, -7, 0, -3, -1]
    for i in range(len(heap)):
        result.append(-heapq.heappop(heap))
    return result

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

# result
[9, 8, 7, 6, 5, 3, 1, 0] # 내림차순 정렬

이 시리즈가 코딩테스트를 공부하는데 조금이나마 도움이 되셨다면 💚를 눌러주세요😉

---

Source

• 이것이 취업을 위한 코딩테스트다 with 파이썬 (나동빈 저)
• 파이썬으로 힙 정렬 구현하기