공부 : 동빈나 유튜브 < 자료구조: 우선순위 큐(Priority Queue)와 힙(Heap) 10분 핵심 요약 >
+ https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
우선순위 큐
: 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
구현 방법
1) 단순히 리스트를 이용하여 구현
2) 힙(heap)을 이용하여 구현 ( 파이썬 - import heapq)
우선순위 큐 구현 방식 | 삽입 시간 | 삭제 시간 |
리스트 | O(1) | O(N) |
힙(Heap) | O(logN) | O(logN) |
단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일 ( 힙 정렬 ) -- O(NlogN)
Heap
- 완전 이진 트리 자료구조의 일종
- 항상 root node를 제거
- 최소 힙(min heap) : root node가 가장 작은 값을 가지기 때문에 값이 작은 데이터가 우선적으로 제거
- 최대 힙(max heap) : root node가 가장 큰 값을 가지기 때문에 값이 큰 데이터가 우선적으로 제거
- 느슨한 정렬 상태를 유지 : 부모노드의 키 값이 자식노드의 키 값보다 큼
- 중복된 값 허용
- 힙에서 부모 노드와 자식 노드 인덱스 관계
왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2
완전 이진 트리
: root node부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리
최소 힙 구성 함수 : Min-Heapify()
(상향식) 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우 위치를 교체
- 힙에 새로운 원소가 삽입될 때 O(logN)의 시간 복잡도로 힙 성질 유지
가장 마지막 위치에 삽입 후 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우 교체
- 힙에서 원소가 제거될 때도 마찬가지로 O(logN)의 시간 복잡도로 힙 성질 유지
원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 합니다.
이후 루트 노드에서부터 하향식으로(더 작은 자식 노드로) Heapify()를 진행
파이썬 힙 정렬 구현 예제
import sys
import heapq
# 기본형태 - min heap
# max heap --> (-)를 붙여서 구현 가능
input = sys.stdin.readline
def heapsort(iterable):
h = []
result = []
# 모든 원소를 차례대로 힙에 삽입
for value in iterable:
heapq.heappush(h, value)
# 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
for i in range(len(h)):
result.append(heapq.heappop(h))
return result
n = int(input())
arr = []
for i in range(n):
arr.append(int(input()))
res = heapsort(arr)
for i in range(n):
print(res[i])
< 더 맵게 >
코딩테스트 연습 - 더 맵게
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같
programmers.co.kr
import heapq
def solution(scoville, K):
heapq.heapify(scoville)
answer = 0
while scoville[0] < K:
min_value = heapq.heappop(scoville)
if scoville :
heapq.heappush(scoville, heapq.heappop(scoville) * 2 + min_value)
answer += 1
else:
return -1
return answer
'study > 알고리즘' 카테고리의 다른 글
[알고리즘 / 자료구조] 트리(Tree) (0) | 2021.11.26 |
---|---|
[알고리즘 / Oracle] 프로그래머스 - 보호소에서 중성화한 동물, 우유와 요거트가 담긴 장바구니 (0) | 2021.11.25 |
[알고리즘 / Oracle] 프로그래머스 - 입양 시각 구하기(2) (0) | 2021.11.24 |
[알고리즘/프로그래머스] 스택/큐 - 다리를 지나는 트럭, 주식가격 (5) | 2021.11.24 |
[알고리즘/프로그래머스] 스택/큐 - 기능개발, 프린터 (0) | 2021.11.23 |