[알고리즘 / 자료구조] 우선순위 큐(Priority Queue)와 힙(Heap)

공부 : 동빈나 유튜브 < 자료구조: 우선순위 큐(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])

 

---

< 더 맵게 >

 

코딩테스트 연습 - 더 맵게

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