[알고리즘] 우선순위 큐 & 힙

큐 ( queue ) : 먼저 들어간 데이터가 먼저나오는 FIFO 구조의 자료구조

 

우선순위 큐 ( priority queue ) : 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조

 

구현하는 3가지 방법

 

1. 배열을 기반으로 구현

2. 연결리스트를 기반으로 구현

3. 힙을 이용하여 구현 - 가장 효율적임

 

힙 : '이진트리 ' 중에서도 '완전 이진 트리'

최대힙 : 부모노드 > 자식노드 

최소힙 : 자식노드 > 부모노드

 

                               C++ 의 priority_queue 의 구조                                 

 

(1) push(1), push(2).  현재 가장 큰 수: 2(top)

 

(2) push(3). 현재 가장 큰 수: 3(top)

 

(3) push(9). 현재 가장 큰 수: 9(top)

 

(4) push(8). 현재 가장 큰 수: 9(top)

 

(5) pop(). 현재 가장 큰 수: 8(top)

                                C++ 을 이용한 priority_queue                                 

priority_queue< int, vector<int>, less<int> > pq;

기본으로는 최대힙 !

less<int> 대신 greater<int> 사용하면 : 최소힙

 

 

참고 : woo-dev.tistory.com/186