Priority Queue / Heap

 

Heap

특정 연산을 빠르게 수행하기 위한 완전 이진 트리(Complete Binary Tree) 자료 구조로서, 여러 값(node) 중 최대값/최소값을 찾는 연산이 빠르다.

 

Max Heap(최대 힙)

값이 가장 큰 노드를 찾기 위한 완전 이진 트리로서 부모 노드의 값이 자식 노드의 값보다 크다. 따라서 루트 노드는 가장 큰 값을 가지게 된다.

 

Min Heap(최소 힙)

값이 가장 작은 노드를 찾기 위한 완전 이진 트리로서 부모 노드의 값이 자식 노드의 값보다 작다. 따라서 루트  노드는 가장 작은 값을 가지게 된다.

 

Priority Queue(우선순위 큐)

먼저 들어오는 데이터가 먼저 나가는 형태가 아닌, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.

일반적으로 Heap을 사용하여 구현한다.

노드 하나의 추가/삭제의 시간 복잡도가 O(logN)이고, 최대값/최소값을 O(1)에 구할 수 있다.