[Python] 힙

힙: 힙 속성을 만족하는 트리

힙 속성

1. 완전 이진 트리( 마지막 레벨 직전의 노드들은 다 채워져 있고, 마지막 레벨은 다 채워질 필요가 없더라도, 왼쪽부터 오른쪽으로 채워져 있어야 함)

2. 최대 힙 -> 부모 노드의 값이 자식 노드의 값보다 크거나 같아야 한다

최소 힙 -> 부모 노드의 값이 자식 노드의 값보다 작거나 같아야 한다

 

파이썬 라이브러리를 사용한 heap

import heapq

 

heapq는 최소 힙을 사용

heapq 메소드	시간 복잡도
heapq.heapify()	O(N)
heapq.heappush()	O(logN)
heapq.heappop()	O(logN)

 

 

heapq 메소드

1. heapq.heapify(리스트)

리스트를 힙 속성을 만족시키도록 만들어준다.

arr = [1, 4, 5, 3, 7, 8]

heapq.heapify(arr)
print(arr)	#[1, 3, 5, 4, 7, 8]

 

 

2. heapq.heappush(리스트, 값)

리스트에 값을 추가고, 힙 속성을 만족 시키도록 heapify 한다

heap = []
for a in arr:
    heapq.heappush(heap, a)
    print(heap)

 

#[1]
#[1, 4]
#[1, 4, 5]
#[1, 3, 5, 4]
#[1, 3, 5, 4, 7]
#[1, 3, 5, 4, 7, 8]

 

 

3. heapq.heappop(리스트)

가장 작은 값의 원소(루트 노드)를 삭제하고 리턴 후 heapify한다

heappop()을 이용하여 힙 정렬을 구현할 수 있다

 

 

힙 정렬

힙의 속성을 이용한 정렬 알고리즘

 

방법

힙을 만든다

-> (루트 노드와 제일 마지막 노드를 바꾼다 -> 제일 마지막 노드는 없는 취급 한다-> 루트노드 heapify) 반복

 

 

힙 속성을 만족하는 트리 [1, 3, 5, 4, 7, 8]의 heappop()

 

#heapify된 리스트
heap = [1,3,5,4,7,8]
heapsort = []

for _ in range(len(heap)):
    heapsort.append(heapq.heappop(heap))
    print(heap)
print(heapsort)

[3, 4, 5, 8, 7]
[4, 7, 5, 8]
[5, 7, 8]
[7, 8]
[8]
[]

[1, 3, 4, 5, 7, 8]

 

오름차순 정렬

heap = [1,3,5,4,7,8]

heapsort = [heapq.heappop(heap) for _ in range(len(heap))]
print(heapsort)

 

내림차순 정렬

 

[::-1] 이용

heap = [1,3,5,4,7,8]

heapsort = [heapq.heappop(heap) for i in range(len(heap))][::-1]
print(heapsort)

[8, 7, 5, 4, 3, 1]

 

 

 

우선순위 큐 구현 시간 복잡도

	데이터 삽입	데이터 추출
정렬된 동적 배열	O(n)	O(1)
정렬된 더블리 링크드 리스트	O(n)	O(1)
힙	O(log(n))	O(log(n))

 

데이터 삽입이 많은 우선순위 큐라면 힙을 사용

데이터 추출이 많은 우선순위 큐라면 정렬된 동적 배열이나 정렬된 더블리 링크드 리스트로 구현

 

 

 

 

https://littlefoxdiary.tistory.com/3

[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기