실전에서 자주 쓰이는 표준 라이브러리(3)_heapq 힙 정렬

 

* 이 글은 『이것이 취업을 위한 코딩 테스트다 with 파이썬』 책을 참고해 적었음을 말씀드립니다.

파이썬에서는 힙(Heap)기능을 사용하기 위해 heapq 라이브러리를 제공한다.
heapq는 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 우선순위 큐 기능을 구현하고자 할 때 사용된다.

 

기본적으로 최소 힙(Min Heap)으로 구성되어 있어 힙에 원소를 넣었다가 빼면 오름차순 정렬이 된다

최소 힙 자료구조의 최상단 원소는 항상 '가장 작은 원소'이기 때문이다

 

 

- 시간 복잡도 : O(NlogN)

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

- heapq.heappop() : 힙에 원소 꺼내기

 

 

1.오름차순 heap 정렬

 

 

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, 6, 2, 0, 4, 7, 5])

print("오름차순 힙 정렬 : ", result)

 

 

오름차순 힙 정렬 :  [0, 1, 2, 3, 4, 5, 6, 7]   

 

 

 

 

2. 내림차순 heap 정렬 : 음수로 바꾸어 표기하고 다시 원래대로 가져오기

 

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, 6, 2, 0, 4, 7, 5])

print("내림차순 힙 정렬 : ", result)

 

내림차순 힙 정렬 :  [7, 6, 5, 4, 3, 2, 1, 0]

 

 

 

 

[참고자료]

- 『이것이 취업을 위한 코딩 테스트다 with 파이썬』 나동빈. 한빛미디어

- https://docs.python.org/ko/3/library/index.html

출처: https://purple-j.tistory.com/203?category=1015351 [Purple's daily record]

실전에서 자주 쓰이는 표준 라이브러리(2)_itertools 순열 조합