우선순위 큐 (Priority Queue)와 힙(Heap)

개념

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다.

배열안의 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다.

 

우선순위 큐를 배울 때 함께 배우는 개념으로 큐, 스택이 있는데 이와 구분될 필요가 있다.  

아래 테이블에 정리되었듯이 자료 추출시점이 삽입시점에 구애받지 않고 우선순위에  따라 추출된다.

자료구조	pop
스택(Stack)	가장 나중에 삽입된 데이터
큐(Queue)	가장 먼저 삽입된 데이터
우선순위 큐(Priority Queue)	가장 우선순위가 높은데이터

구현

우선순위 큐의 구현방법은 여러가지가 있다.

List를 이용하는 방법도 가능하고, 숫자의 경우 heap구조의 활용이 시간복잡도상 유리한 부분이 있다. 

 

heap구조의 경우 정렬시 시간복잡도가 O(logN)이기 때문에, 구조를 유지한채 배열에 삽입, 삭제하는데 O(logN)이 소요된다.

(List의 경우 삽입 O(1) 삭제 O(N))  

 

heap 자료구조에 대해 간단히 설명하면 하기 이미지와 같다.

핵심은 2가지 이다.

0. 자료구조가 이진트리의 형태를 띄고 있음

1. 부모와, 자식노드간의 대소관계 구분이 일관됨.

2. 같은 레벨상의 자식노드간의 배열은 상관없음

3. 새로운 자료가 추가, 삭제되어도 힙의 형태 유지 (0, 1, 2 조건)

Python의 경우 자료구조의 Heapify를 쉽게하기 위한 내장함수 heapq를 지원한다. 

heap자료구조에는, 최대값이 root에 있는 Max-heap, 최소값이 root에 있는 Min-heap이 있는데, 파이썬의경우 Min-heap만 지원된다. 따라서 Max-heap구현을 위해서는 별도의 작업을해야한다. 이와 관련된 백준 알고리즘 문제는 다음과 같다.

#heappush(arr, value)는 array에 value를 삽입한다. heap이 이루어진 상태로 삽입된다.

#heappush는 array에서 root를 pop한다. (값 반환) 반환 후 heap이 유지된다.

 

 

import sys
import heapq  # heapq 내장 라이브러리를 사용. heappush(arr, value)   // heappop(h)  
input=sys.stdin.readline
N=int(input())
arr=[]

for i in range(N):
    A=int(input())

    if A==0 and arr:
        print(-heapq.heappop(arr))
    elif A==0:
        print('0')
    else:
        heapq.heappush(arr,-A)


#heappush(arr, value)는 array에 value를 삽입한다. heap이 이루어진 상태로 삽입된다.
#heappush는 array에서 root를 pop한다. (값 반환) 반환 후 heap이 유지된다.

https://www.acmicpc.net/problem/11279

11279번: 최대 힙