[Python] Heapq 모듈 사용하기

Heapq 모듈이란?

• 파이썬 heapq 모듈은 우선순위 큐 알고리즘이라고도 하는 힙(heap) 큐 알고리즘의 구현을 제공한다.

• 기본적으로 Min-priority-queue 구조를 가지고 있다.

• heapq는 내장 모듈로 별도의 설치 작업 없이 바로 사용할 수 있다.

    import heapq

힙(heap)에 요소추가 : heappush(heap, item)

heapq 모듈은 리스트를 최소 힙처럼 다룰 수 있도록 하기 때문에, 빈 리스트를 생성한 후 heapq의 함수를 호출할 때마다 리스트를 인자에 넘겨야 한다.

• 힙(배열)에 요소(item)을 추가

    import heapq
  
    heap = []
    heapq.heappush(heap, 50)
    heapq.heappush(heap, 10)
    heapq.heappush(heap, 20)
  
    print(heap)
  
    # print 결과값 => Heap 구조로 변했다.
     [10, 50, 20]

힙(heap)의 요소삭제 : heappop(heap)

• heappop 함수는 가장 작은 원소를 힙에서 제거함과 동시에 그를 결괏값으로 리턴한다.

• 비어 있는 경우 IndexError가 호출된다.

    import heapq
  
    heap = []
    heapq.heappush(heap, 50)
    heapq.heappush(heap, 10)
    heapq.heappush(heap, 20)
  
    result = heapq.heappop(heap)
  
    print(result)
    print(heap)
  
    # print(result) 결과값
     10
    # print(heap) 결과값
    [20, 50]

• 원소를 삭제하지 않고 가져오고 싶으면 [0] 인덱싱을 통해 접근하면 된다.

• [0] 인덱싱을 통해 접근하고난 후에도 heap 은 유지된다.

    result2 = heap[0]
  
    print(result2)
    print(heap)
  
    # print(result2) 결과값
     20
    # print(heap) 결과값
    [20, 50]

리스트(list)를 힙(heap)으로 변환 : heapify(x)

• heapify 함수를 사용하면 이미 생성해둔 리스트를 즉각적으로 힙 자료형으로 변환할 수 있다.

    import heapq
  
    heap = [50 ,10, 20]
    heapq.heapify(heap)
  
    print(heap)
  
    # print 결과값 => 
    [10, 50, 20]

최대 힙(MaxHeap) 구현하기

• 파이썬의 heapq 모듈은 최소 힙으로 구현되어 있기 때문에 최대 힙 구현을 위해서는 트릭이 필요하다.

방법 1. - 값을 집어넣고 꺼낼 때도 -를 붙여서 꺼내기

• 단순히 -를 붙여주는 작업만 하더라도 충분히 maxheap 의 용도처럼 사용할 수 있다.

    a = [3,5,2,4,1]
    testheap = []
    for i in a:
         heapq.heappush(testheap, -i)
    for i in range(5):
         print(-heapq.heappop(testheap))
  
    # print 결과 =>
    5
    4 
    3
    2
    1

방법 2. 튜플 이용하기

• 힙에 원소를 추가할 때 (-item, item)의 튜플 형태로 넣어준다.

• heapq 는 튜플의 첫번째 요소를 기준으로 정렬하므로 최소 힙으로 구현된 heapq 모듈을 최대 힙 구현에 활용할 수 있다.

• 실제 원소 값은 튜플의 두 번째 자리에 저장되어 있으므로 [1] 인덱싱을 통해 접근하면 된다.

    a = [3,5,2,4,1]
    testheap = []
    for i in a:
        heapq.heappush(testheap, (-i,i))
    for i in range(5):
        print(heapq.heappop(testheap)[1])
  
    # print 결과 =>
    5
    4
    3
    2
    1

참조

• https://littlefoxdiary.tistory.com/3
• https://programming119.tistory.com/85