Heap 과 우선순위 큐(Priority Queue)

우선순위 큐는 일반적인 Queue 와는 다르게, 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나온다.

 

우선순위 큐는 Heap이라는 자료구조를 가지고 구현한다.

 

Heap이란?

 - 힙은 완전 이진트리 형태이다.

 - 모든 노드에 저장된 값들은 자식 노드들보다 우선순위가 크거나 같다.

 

MaxHeap은 완전 이진트리이면서, 루트 노드로 올라갈수록 저장된 값이 커지는 구조이다.

MinHeap은 완전 이진트리이면서, 루트 노드로 올라갈수록 저장된 값이 작아지는 구조이다.

 

출처 : https://www.geeksforgeeks.org/heap-data-structure/