[python] - 힙 자료구조와 heapq

조은지·2021년 9월 15일
0

출처 - 이것이 코딩테스트다 with Python

내가 하면 힙!! ㅈㅅ합니다.

힙 자료구조

힙 자료구조는 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나이다.

우선순위 큐

먼저 스택과 큐의 방식을 떠올려보자.
스택 - 가장 나중에 삽입된 데이터를 가장 먼저 삭제
큐 - 가장 먼저 삽입된 데이터를 가장 먼저 삭제

우선순위 큐? 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다.
이러한 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다.

파이썬에서는 우선순위 큐를 구현할 수 있는 라이브러리를 제공한다.

  • PriorityQueue 혹은 heapq

일반적으로 heapq가 더 빠르게 동작하기 때문에 수행시간이 제한된 상황에서는 heapq를 사용한다.
(검색을 해본 결과 priorityQueue는 완벽한 정렬을 제공하고, heapq는 느슨한 정렬을 제공하기 때문이라고 한다.)

최소힙과 최대힙

먼저 힙은 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.

최소힙 - 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리
(값이 낮은 데이터가 먼저 삭제)
최대힙 - 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
(값이 큰 데이터가 먼저 삭제)

heapq

일반적으로 우선순위 큐 라이브러리에 데이터의 묶음을 넣으면, 첫번째 원소를 기준으로 우선순위를 설정한다. 따라서 데이터가 (가치, 물건)으로 구성된다면 '가치'값이 우선순위 값이 된다.

heapq도 마찬가지이다.

heapq 모듈과 사용방법

heapq 모듈은 이진트리 기반의 최소힙 자료구조를 제공한다.

import heapq

heap = [] #빈 리스트를 먼저 생성

#push
heapq.headpush(heap,3) #heap리스트에 최소힙 방식으로 값을 삽입
heapq.headpush(heap,1)
heapq.headpush(heap,2)
heapq.headpush(heap,4)

print(heap) #오름차순으로 정렬이 된다. 

#pop
print(heapq.heappop(heap)) #가장 작은 숫자부터 pop이 된다. 

#기존 리스트를 힙으로 변환
h2 = [3,1,4,2]

heapq.heapify(h2)
print(h2)
[1,2,3,4]
1

[1,2,3,4]

만약 heapq를 이용해서 최대힙을 만들고 싶다면 값을 음수로 만드는 방법이 있다.

+) (가치, 물건)쌍으로 저장을 한다면?

#ex- [가격, 색깔]에서 가격을 기준으로 최소힙정렬을 하고 싶을 때

h=[]
heapq.heappush(h,(10000,'yellow'))
heapq.headpush(h,(5000,'red'))
heapq.headpush(h,(15000,'blue'))

print(h)
[[5000, 'red'],[10000,'yellow'],[15000, 'blue']]

0개의 댓글