heap / heapq 모듈

다익스트라 알고리즘을 공부하면서 알게된 모듈 heapq

 

이걸 알아야 다익스트라를 이해할 수 있을 것 같아서 heap과 heaq부터 찾아보았다.

 

---

Heap

• Heap은 Complete Binary Tree를 기본으로 가지는 자료구조
• 일반적으로 array로 구현하는 것이 좋음
• Heap 은 최댓값 또는 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됨
• 시간복잡도: O(log₂N)
• Heap은 다음과 같은 속성(property)를 만족함
  • A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소관계가 성립
• 종종 priority queue를 보충하는대에 사용

(참고 블로그 : https://brownbears.tistory.com/391)

Heap

 

---

heapq 모듈

최소 힙(min heap)기능 만으로 작동

 

heappush() : 원하는 값을 추가할 수 있게 해준다. 

코드

import heapq

heap = []

heapq.heappush(heap, 4)
heapq.heappush(heap, 2)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)

print(heap)

결과 : 4, 2, 3, 7 으로 추가했는데 [2, 4, 3, 7]순으로 저장되어 있다. (heapq를 통해 값을 추가하면 대소를 비교하여 정렬이 이뤄진다.)

[2, 4, 3, 7]

 

 

heappop() : 값 빼기.

print(heapq.heappop(heap))
print(heap)

결과 : heapq에서는 우선순위가 있어 우선순위가 가장 높은(가장 작은 숫자)가 제일 배열의 앞에 배치되었기 때문에 2가 빠짐.

2
[3, 4, 7]

 

heapify() : 넘겨준 리스트 인자를 heap에 맞게끔 구조를 정렬한다

코드

heap2 = [5,6,555,66,1123,1]
print(heapq.heapify(heap2))
print(heap2)

결과 

None
[1, 6, 5, 66, 1123, 555]

 

 

최대 힙(max heap)구현하기

heap을 생각하기 이전에 간단한 예로 [20, 10, 30] 리스트가 있다고하자. 이 리스트에 첫번째에는 무조건 가장 작은 값이 와야한다고 해보자. 그렇다면 당연히 첫번째 자리에 10이 올 것이다. 그렇다면 살짝만 바꿔서 [-20, -10, -30] 리스트로 바꿔보고 똑같이 적용해본다면?

첫번째 자리에 -30이 와야한다. 즉 -만 붙여주면 가장 큰 숫자가 가장 작은 숫자가 된다. 이 방법을 사용하면 최대 힙 구현이 간단하게 가능하다.

nums = [6,7,1,23,4,55,0]
heap = []

for num in nums:
    heapq.heappush(heap, (-num, num))

while heap:
    print(heapq.heappop(heap)[1], end=' ')

결과  - heappop을 사용하여 heap에서 값을 빼왔기 때문에 반복문이 진행되는 동안 heap은 계속 우선순위가 바뀌어 값이 큰 순서대로 숫자가 빠져 나온다. (이 과정을 함수로 만들고 리스트를 반환해주는 구조라면 힙 정렬 함수가 된다.)

55 23 7 6 4 1 0 

 

 

n번째 최소/최대 값 구하기

위에서 사용한 최대값 구하는 방법에서 출력해준 문장을 활용하면 된다. 원하는 만큼 반복만 해주면 된다.

nums = [6,7,1,23,4,55,0]
findSmall = 3; findBig = 4

heapq.heapify(nums)

heap = []
for num in nums:
    heapq.heappush(heap, (-num, num))

findNumS = None; findNumB = None

for _ in range(findSmall):
    findNumS = heapq.heappop(nums)

for _ in range(findBig):
    findNumB = heapq.heappop(heap)[1]

print(f'3th Small Num : {findNumS} \t/\t 4th Big Num : {findNumB}')

결과 - nums를 오름차순 정렬하면 [0, 1, 4, 6, 7, 23, 55]. 잘 나왔음을 확인할 수 있었다.

3th Small Num : 4   /   4th Big Num : 6