큐는 선입선출, 먼저 들어간 데이터가 먼저 나온다.
우선순위 큐는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나온다. (우선순위가 다른 데이터 뿐만 아니라 같은 데이터가 존재할 수도 있다)
<구현 방법>
1. 배열을 기반으로 구현하는 방법
2. 연결리스트를 기반으로 구현하는 방법
3. 힙(heap)을 이용하는 방법
배열이나 연결리스트로 구현할 경우 간단하게 구현이 가능하지만, 데이터 삽입과 삭제 과정에서 데이터를 한 칸씩 당기거나 밀어야 하는 연산을 계속 하여야 함.
또 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야 한다.
연결리스트의 경우, 삽입의 위치를 찾기 위해 첫번째 노드부터 시작해 마지막 노드에 저장된 데이터와 우선순위 비교를 진행해야 할 수도 있다. -> 성능 저하
그래서 일반적으로 힙을 이용해 구현한다.
*최대힙이란?(max heap)
-최대힙은 부모 노드가 자식노드 보다 값이 큰 완전 이진트리를 의미한다.
-즉, 모든 부모 노드가 자식보다 값이 커야한다.
-최대힙의 root node는 항상 최대값을 가진다.
-전체 트리가 최대 힙 구조를 유지하도록 자료구조를 만들어야 한다.
-삽입할 원소는 완전 이진트리를 유지하는 형태로 순차적으로 삽입된다.
-삽입 이후에는 루트 노드까지 거슬러 올라가면서 최대힙을 구성한다.(상향식)
-즉, 부모노드와 비교를 해서 부모노드가 삽입한 노드의 값보다 작다면 교체한다.(logN의 시간복잡도를 가진다)
삭제 할 때는 루트노드를 삭제하고, 가장 마지막 원소를 루트 노드의 위치로 옮겨준다.
먼저, 루트노드인 9를 삭제한다.
가장 마지막 원소를 루트 노드의 위치로 옮긴다.
이제 교체된 루트노드부터 하향식으로 내려가면서 최대 힙을 구성한다.(하향식)
현재노드보다 큰 값이 있으면 교체한다.
#include <stdio.h>
#define MAX_SIZE 10000
void swao(int *a, int *b){
int temp=*a;
*a=*b;
*b=temp;
}
typedef struct priorityQueue{
int heap[MAX_SIZE];
int count;
}priorityQueue;
#include <stdio.h>
#define MAX_SIZE 10000
void swap(int *a, int *b){
int temp=*a;
*a=*b;
*b=temp;
}
typedef struct priorityQueue{
int heap[MAX_SIZE];
int count;
}priorityQueue;
void push(priorityQueue *pq, int data){
if(pq->count >= MAX_SIZE) return;
pq->heap[pq->count] = data; //완전 이진트리의 마지막 원소에 데이터 삽입
int now = pq->count; //삽입된 데이터에 해당하는 노드의 인덱스
int parent = (pq->count-1)/2; //삽입된 노드의 부모노드
while(now > 0 && pq->heap[now] > pq->heap[parent]) {
swap(&pq->heap[now], &pq->heap[parent]); //부모노드와 삽입된 노드 교체
now = parent;
parent = (parent-1)/2;
}
pq->count++;
}
int pop(priorityQueue *pq){
if(pq->count <= 0) return -9999;
int res = pq->heap[0];
pq->count--;
pq->heap[0] = pq->heap[pq->count];
int now = 0, leftChild = 1, rightChild = 2;
int target = now;
//원소가 존재할 때 까지만 반복
while(leftChild < pq->count) {
if(pq->heap[target] < pq->heap[leftChild]) target = leftChild;
if(pq->heap[target] < pq->heap[rightChild] && rightChild < pq->count) target = rightChild;
if(target==now) break;
else{
swap(&pq->heap[now], &pq->heap[target]);
now = target;
leftChild = now * 2 + 1;
rightChild = now * 2 + 2;
}
}
return res;
}
int main(void) {
int n, data;
scanf("%d", &n);
priorityQueue pq;
pq.count = 0;
for(int i = 0; i < n; i++) {
scanf("%d", &data);
push(&pq, data);
}
for(int i = 0; i < n; i++) {
int data = pop(&pq);
printf("%d ", data);
}
return 0;
}