우선순위 큐

• 우선순위를 가진 항목들을 저장하는 큐
• 순위가 높은 데이터가 먼저 나가게 됨
• 힙을 이용해서 구현

스택	가장 최근에 들어온 데이터
큐	가장 먼저 들어온 데이터
우선순위큐	가장 우선순위가 높은 데이터

힙

• key(A) >= key(B) (중복 허용)
• 부모 노드 A는 자식 노드 B보다 크거나 같은 완전이진트리
• 더미라는 의미

최대 힙(max heap)

• key(부모노드) >= key(자식노드)
• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
• root가 최대값
  

최소 힙(min heap)

• key(부모노드) <= key(자식노드)
• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전이진트리
• root가 최소값
  

힙 클래스

• Heap Node 클래스
• Max Heap 클래스
• 힙의 구현은 배열로 한다

삽입 연산

Upheap algorithm (min heap)

• 삽입된 노드에서 루트까지의 경로에 있는 노드들을 비교하고 교환

• 최소힙: 키가 부모 노드보다 크거나 같으면 upheap 종료
  

• 최대힙: 키가 부모 노드보다 작거나 같으면 upheap 종료
  

최대힙에서의 삭제 연산

• 가장 큰 키 값을 가진 노드를 삭제
• 최대 힙에서는 항상 루트가 삭제
• 루트 삭제 후 힙 성질을 만족하도록 재구성한다
• 재구성은 downheap으로 해결

Heap Sorting

힙을 이용한 정렬 = 힙 정렬

최소 힙의 경우

1. 먼저 정렬해야 할 n개의 요소들을 최소 힙에 삽입한다
2. 한번에 하나씩 요소를 힙에서 삭제하여 출력한다
3. 삭제된 요소들은 오름차순 정렬된다

최대 힙의 경우

1. 내림차순으로 정렬된다
2. 오름차순으로 정렬하기 위해서는 뒤에서부터 나열하면 된다

C++ Priority Queue Container

Type, Container, Compare을 순서대로 작성

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

Type

priority_queue에 저장되는 요소들의 자료형

Container

우선순위 큐에서 사용할 컨테이너 지정

Compare

요소들을 저장하는 기준

less<int> // 최대힙 (기본값)
greater<int> // 최대힙

생성자

priority_queue();
priority_queue(InputIterator first, InputIterator last); // 벡터의 시작과 끝을 가리키는 반복자

pq(v.begin(), v.end()); // v벡터의 요소들을 기반으로 우선순위 큐를 초기화

Function

• size() : 크기
• top() : 우선순위 큐의 top을 알려준다(=root)
• pop() : 우선순위 큐의 top을 삭제한다
• push() : 우선순위 큐에 추가한다
• empty() : 우선순위 큐가 비어있는지를 확인한다