우선순위 큐 (Priority Queue)
•
데이터를 저장할 때 우선순위를 가진 데이터를 저장하며, 데이터를 꺼낼 때 우선순위가 높은 순으로 데이터를 가져온다
스택, 큐 와의 차이점
•
스택
◦
가장 나중에 들어온 데이터가 가장 먼저 나온다 (LIFO)
•
큐
◦
가장 먼저 들어온 데이터가 가장 먼저 나온다 (FIFO)
•
우선순위 큐
◦
가장 우선순위가 높은 데이터가 가장 먼저 나온다
일반적인 큐는 선형적인 형태를 가지고 있지만, 우선순위 큐는 완전이진트리 형태를 가지고 있으며, 최대 힙(Max Heap) 을 이용해 구현해야한다.
힙 (Heap)
•
최대 힙 (Max Heap)
◦
부모 노드의 키 값이 자식 노드의 키 값보다 ‘크거나 같은’ 완전 이진트리
▪
부모노드의 키 값 ≥ 자식노드의 키 값
•
최소 힙 (Min Heap)
◦
부모 노드의 키 값이 자식 노드의 키 값보다 ‘작거나 같은' 완전 이진트리
▪
부모노드의 키 값 ≤ 자식노드의 키 값