힙 정렬

힙정렬이란 ?
리스트나 배열을 먼저 최소힙이나 최대힙으로 바꾸고 원소들을 순서대로 정렬하는 방법이다.
최소힙은 최소값을 구할 때, 최대힙은 최대값을 구할 때 사용한다.

 

 최대힙이란?
완전 이진 트리이면서, 부모노드는 자식 노드보다 크다. 

삽입) 새 노드에 삽입이 되고 나서, 최대 힙이 될 때까지 위로 올라가는 과정을 반복한다.

부모 노드보다 값이 클 경우, 서로 교환하면서 위로 올라가는 과정을 반복

삭제) 힙의 루트에서 삭제한다. 그러면 루트가 비어있는 상태가 되고, 가장 마지막 노드를 루트 노드로 올린다.
이후 새로 올린 노드가 제자리를 찾아갈 수 있도록 연산을 반복한다.

*완전 이진 트리

노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리이다.

2. 최소힙이란?

완전 이진 트리이면서, 각 노드의 키 값이 그 자식의 키 값보다 크지 않다.

 

3. heapq 모듈

파이썬에서는 heapq 모듈을 사용해서 최소 힙과 최대 힙을 구현할 수 있다.

내부 메소드) heappush와 heappop이 있다.

heappush(heap,item): 힙 불변성을 유지하면서, item 값을 heap으로 push 해주는 메소드이다.

heappop(heap): 힙 불변성을 유지하면서, heap에서 가장 작은 항목을 pop하고 반환해주는 메소드이다.

 

4. 구현

 

* 최소힙의 구현

import heapq
heap=[]

for i in range(1,6):
	heapq.heappush(heap,i)
    
for i in range(5):
	print(heapq.heappop(heap))

 

* 최대 힙의 구현

 

import heapq

heap=[]
values=[1,5,3,2,4]

for value in values:
	heapq.heappush(heap,-value)

for i in range(5):
	print(-heapq.heapop(heap))

 

 

참고)

https://it-garden.tistory.com/128