우선순위 큐와 힙

📖우선순위큐와 힙 내용 정리

우선순위 큐와 힙이 같은 개념이라고 오해할 수 있지만 둘은 서로 다른 개념이다.
우선순위 큐와 힙에 대해 알아보기 전, 이를 이해하기 위해 알아둬야할 개념은 다음과 같다.
* 큐 : 먼저 들어온 데이터가 먼저 나가는 형식(First In First Out)의 자료구조이다.
* 완전이진트리 : 왼쪽부터가 오른쪽으로 노드가 채워지는 형식이며, 마지막 레벨을 제외한 모든 레벨이 채워져 있는 형태이다.

• '우선순위 큐'의 특징
• -일반적인 큐와 다르게 우선순위의 개념을 큐에 적용한 자료구조
  -들어간 순서에 상관 없이 우선순위를 근거로 dequeue 연산이 진행된다.
  -두 요소의 우선 순위가 동일한 경우 대기열에서 해당 요소의 순서에 따라 진행된다.
• '힙'의 특징
• -완전 이진 트리
  -최대 힙: 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 즉 루트 노드에 저장된 값이 가장 커야 한다.
  (부모 key >= 자식 key)
  -최소 힙: 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 즉 루트 노드에 저장된 값이 가장 커야 한다.
  (부모 key =< 자식 key)
  -부모노드와 자식노드 간의 관계
  :왼쪽 자식노드 인덱스 = 부모의 인덱스 x 2
  :오른쪽 자식노드 인덱스 = 부모의 인덱스 x 2 + 1
  :부모노드 인덱스 = 자식노드 인덱스 / 2

📖C++를 이용한 우선순위큐 프로그래밍 방법 정리

우선순위 큐 구현 방법

-배열 기반 구현

enqueue(): 새 데이터를 대기열에 삽입하는 데 사용

dequeue(): 대기열에서 우선 순위가 가장 높은 요소를 제거

peek()/top(): 대기열에서 가장 높은 우선 순위 요소를 제거하지 않고 가져오는 데 사용

 

-연결리스트 기반 구현

push(): 새 데이터를 큐에 삽입하는 데 사용

pop(): 우선순위가 가장 높은 요소를 대기열에서 제거

peek()/top(): 대기열에서 가장 높은 우선 순위 요소를 제거하지 않고 가져오는 데 사용-힙 기반 구현

insert(p): 우선 순위가 p인 새 요소를 삽입

extractMax(): 최대 우선 순위를 가진 요소를 추출

remove(i): i가 가리키는 요소를 제거

getMax(): 최대 우선 순위를 가진 요소를 반환

changePriority(i, p): i to p가 가리키는 요소의 우선순위를 변경

#include <iostream>
#include <queue>
#include <tuple>
#include <string>
#include <fstream>

using namespace std;
void MaxHeapSorting(int a[], int n) { 
	priority_queue <int> maxHeap;
	for (int i = 0; i < n; ++i)
		maxHeap.push(a[i]);
	for (int i = 0; i < n; i++) {
		a[i] = maxHeap.top();
		maxHeap.pop();
	}
}
void MinHeapSorting(int a[], int n) { 
	priority_queue<int, vector<int>, greater<int>>minHeap;
	for (int i = 0; i < n; ++i)
		minHeap.push(a[i]);
	for (int i = 0; i < n; ++i) {
		a[i] = minHeap.top();
		minHeap.pop();
	}
}

💻문제 풀이

• 백준 1966번 - 프린터 큐

#include <iostream>
#include <queue>
#include <fstream>
using namespace std;

int main() { // 메인함수

	// 사용될 변수 선언
	int num_test_cases;
	int N; 
	int M;
	int temp_priority; int tp;
	int temp_order;
	int cnt;
	
	ifstream  fin("Prob_1966.txt"); // txt파일 불러오기
	fin >> num_test_cases;

	for (int i = 0; i < num_test_cases; ++i) {
		fin >> N >> M;
		cnt = 0;
		queue<pair<int, int>> data;
		priority_queue <int> priority_data;
		
		for (int j = 0; j < N; ++j) {
			fin >> temp_priority;
			data.push({ j,temp_priority });
			priority_data.push(temp_priority);
		}

		while(!data.empty()) {
			
			tp = data.front().first;
			temp_order = data.front().second;
			data.pop();
			
			if (priority_data.top() == temp_order) {
				priority_data.pop();
				cnt++;

				if (tp == M) {
					cout << cnt << endl;
					break;
				}
			}
			else {
				data.push({ tp, temp_order });
			}
		}
	}
	fin.close(); // txt파일 닫기
	return 0;
}