[TIL] priority Queue / Heap

1.heap

여러 값들 중 우선순위가 중요할 때 사용하는 자료구조로 완전 이진 트리 형태를 띔.

이진트리 종류

heap이 적재되는 구조

힙이 가장 많이 사용되는 자료 구조는 각원소가 튜플로 된 리스트나, 딕셔너리가 될 것 같다.

ex)
[(7:양치하기), (2:밥먹기), (9:간식먹기), (1:잠자기), (3: 공부하기), (13: 산책하기)

이런 식의 예제가 있다고 치자.

우선순위:행동 이라는 구조를 가진 튜플을 heapify하려고 할 때,

힙 구조에 하나씩 넣어 우선순위 순으로 행동하고자 한다.

Heap PUSH

최초로 Heap Push 시 가장 최상단에 누적.

다음 누적

부모노드와 비교 후 우선순위가 높으면 위치 교체

다음 누적

비교 시 부모노드 우선순위가 높기 때문에 변경 X

다음 누적

비교 시 부모노드보다 우선순위가 높으므로 위치 교체

교체 후 다시한번 부모노드와 비교 (부모노드가 없을 때 까지)

이런 느낌으로 완전 이진트리로 채워나감.

Heap pop

이렇게 행동 우선순위로 정렬된 힙구조가 있다 치자
우리가 컴퓨되었다고 가정하고 하나씩 행동해보자

가장 높은 우선순위를 가진 수를 pop 해서 동작 했다.

(힙 구조는 항상 이진트리 형식에서 level 1인 녀석만 Pop을 한다.)

부모노드를 비웠으니 채워야 한다

heap 안에 있는 가장 끝 인덱스의 값을 가져온다

자식노드 중 우선순위가 높은 녀석 석 선택

선택한 자식노드를 부모노드와 교체 한다.

자식노드가 없을때까지 반복한다.

끝

2. 우선순위 Queue

Queue는 FIFO(선입선출) 형식으로 먼저나오는 값이 먼저 나가는 구조이지만 우선순위 queue는 들어오는 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나간다.

heap구조를 활용하여 우선순위 queue는 heap 구조를 이용하는 것이 가장 효율적

백준 최대 힙

import heapq
import sys


heap=[0]


n = int(input())
for _ in range(n) :
    input1 = int(sys.stdin.readline())
    
    if input1 == 0:
        if heap[0] != 0:
            print(-heapq.heappop(heap))
        else:
            print(heap[0])
    
    else:
        heapq.heappush(heap,-input1)
            

heapq 모듈

heappush([배열],값)

heap에 value 삽입

(파이썬은 min heap만 지원)

value에 -를 붙여 음수로 저장하면 최대힙으로 구현 가능

heappop([배열])

heap최상단(부모노드) pop

(파이썬은 min heap만 지원)

pop()에 -를 붙여 음수로 가져오면 -(-x) 같인 부호가 변경되어 정수로 출력 가능.

(-heapq.heappop(heap)