# heap

마지막으로 힙에 대해서 정리하고자 합니다. 힙은 우선순위 큐라고도 하며 최소 힙과 최대 힙의 개념이 존재합니다. 이를 파이썬 코드로 작성하겠습니다. 여기서는 PriorityQueue()를 사용합니다.

 

최소 힙

from queue import PriorityQueue

hp = PriorityQueue()

hp.put(40)
hp.put(10)
hp.put(30)
hp.put(20)

print("현재 힙의 값은: ", hp.queue)

remove_first = hp.get()
print("가장 우선순위 값: ", remove_first)

현재 힙의 값은:  [10, 20, 30, 40]
가장 우선순위 값:  10

코드 상으로 40 - 10 - 30 - 20 순서로 값을 넣었으나 값을 확인해보면 위의 결과값처럼 보이게 됩니다. PriorityQueue()에서는 get()이라는 모듈을 통해 가장 우선에 있는 값을 나가도록 합니다.

 

정렬된건가

형태를 보면 마치 정렬된 것처럼 보일 수도 있습니다. 저도 처음에는 sort()와 같은 정렬함수를 그럼 안써도 되는건가? 라는 생각을 했지만 이는 틀린 생각이었습니다. 정렬이 된 것처럼 보이는 것일뿐, 실제로는 그렇지 않다고 합니다. 

 

다시말해, sort()와 같은 정렬함수는 정말 정렬을 진행한 것이고 PriorityQueue()는 우선순위대로 먼저 조정을 진행한 것일뿐 실제 정렬을 진행한 상태가 아니라는 뜻입니다.

 

최대 힙

from queue import PriorityQueue

hp = PriorityQueue()

hp.put([-40, 40])
hp.put([-10, 10])
hp.put([-30, 30])
hp.put([-20, 20])

print("현재 힙의 값은: ", hp.queue)

remove_first = hp.get()
print("가장 우선순위 값: ", remove_first[1])

현재 힙의 값은:  [[-40, 40], [-20, 20], [-30, 30], [-10, 10]]
가장 우선순위 값:  40

최대 힙을 구현하는 경우는 모듈 상으로 존재하지 않습니다. 그래서 최대 힙을 구현할 때는 최소 힙의 특성을 활용해서 이를 만들어주는 매커니즘이 필요합니다.

 

최대 힙을 구현할 때는 넣으려는 값에 음수를 붙여주고 이를 배열로 처리해서 넣습니다. [-a, a] 이런 식으로 넣는다면 -a를 비교하는 식으로 진행할 것입니다. 그러면 가장 큰 값이 결국 음수가 붙어 가장 작은 값이 되기에 최소 힙을 응용한 최대 힙처럼 동작하게 만들 수 있습니다.