python heapq 사용법 힙 자료구조 사용하기

python은 기본적으로 구현된 heapq 모듈이 있어 바로 가져다 쓸 수 있다. 

python 표준 라이브러리에 내장 모듈이 기본적으로 포함되어있어, 별도 설치없이 `import heapq`로 바로 사용 가능하다.

 

 ⬇️ python heap queue algorithm 공식문서 ⬇️

https://docs.python.org/3/library/heapq.html

heapq — Heap queue algorithm

 

우선 heap 자료구조를 만드려면 이 heapq 모듈을 사용해서 리스트를 heap 구조를 만들 수 있다.

 

방법1. heapq.heapify() 사용

기존에 존재하는 리스트를 바로 heap구조로 변환할 때 사용 

`heapq.heapify(list)`로, 인자에 리스트를 전달한다.

 

import heapq 

nums = [2,7,4,1]
newHeap = heapq.heapify(nums) # ❌
print(newHeap)  # None
print(nums)  # 힙 구조로 변경된 리스트 [1, 2, 4, 7]

 

여기서 처음에 나는 4번 줄처럼 새로 변수에 할당하려고 했다. 이러면 heap으로 바뀐애가 새로 할당되겠지? 생각했는데, 그렇지 않다.

`heapq.heapify(nums)` 함수는 인자로 전달된 리스트 nums를 직접 수정하지, 새로운 힙 객체를 반환하지 않는다.

 

즉, heapq.heapify(nums)를 하면 nums 리스트를 직접 힙 구조로 바꿔준다.

heapq.heapify(nums)의 반환값은 None으로 새로 할당된 변수 newHeap에는 아무것도 할당되지 않고, nums 리스트가 내부적으로 min-heap으로 재정렬된 힙 구조를 가진다. 

 

✅ 아래처럼 사용

import heapq 

nums = [2,7,4,1]
heapq.heapify(nums) ✅
print(nums)  # 힙 구조로 변경된 리스트 [1, 2, 4, 7]

 

방법2. heapq.heappush() 사용

heappush() 함수를 사용해서 리스트에 요소를 하나씩 추가할때 사용한다.

`heapq.headpush(list, value)`로 첫번째 인자에 리스트, 두번째 인자에 추가하려는 요소를 전달한다.

 

import heapq

heap = heapq.heappush([], 2)  # ❌ 잘못된 사용
print(heap)  #None

 

하지만 위와 같이 사용하면 안된다.

방법1 예제와 마찬가지로 3번 라인처럼 heap이라는 변수에 재할당하면 이 변수의 리턴값은 None이 된다.

 

✅ 아래처럼 사용

heap = []                    # 내가 사용할 리스트를 직접 선언
heapq.heappush(heap, 2)      # 이 리스트를 힙처럼 사용
heapq.heappush(heap, 7)
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)

print(heap)      # 내부 구조 (예: [1, 2, 4, 7])

minVal = heapq.heappop(heap)
print(minVal)   # 1
print(heap)      # [2, 4, 7]

 

정리

• python `heapq` 모듈은 in-place 방식으로 리스트를 힙 자료구조로 변환한다. 즉, 전달받은 리스트를 직접 조작하여 수정한다.
• 힙구조로 사용하고싶은 리스트를 우리가 명시적으로 정의해서 관리해야한다.
  자세히 설명하면, heapq 모듈은 전용 힙 자료구조 클래스가 없다. 그래서 대신에 일반적인 파이썬 리스트를 힙처럼 사용하게 되어있다. 
  따라서 heap 전용 객체를 생성하는게 아니라, 우리가 리스트를 만들어서, 그 리스트를 heap으로 관리해야한다는 뜻이다. 
• `heqpq`는 마치 `list`를 힙 모드로 작동하게 하는 도구이다. heapq를 쓴다고 자동으로 heap 객체를 생성해주는게 아니라, 우리가 먼저 리스트를 만들고 그 리스트를 heapq에 넘겨주어 힙 자료구조로 변환된 리스트를 사용하는 것이다.