힙(Heap)을 통한 우선순위 큐 구현

우선순위큐 (Priority Queue)

우선순위큐는 우선순위에 따라 정렬되어 순차적으로 처리되는 자료구조이다.

우선순위큐는 Heap을 통해 구현이 가능하다.

 

힙(Heap)

Heap은 '완전 이진 트리'로 구현된 트리구조의 자료구조이다.

Max Heap인지 Min Heap인지 여부에 따라 부모와 자식은 절대적인 정렬상태를 가진다.

+) 형제(sibiling)끼리의 정렬은 관계가 없다

 

O(log2n)의 준수한 시간복잡도를 가진다.

 

 

최대(Max) 힙을 통한 우선순위 큐 구현은 다음과 같다.

 

---

#include <iostream>
using namespace std;
#define MAX_SIZE 99999

//삽입과정은 완전 이진트리를 유지하는 형태로 순차적 삽입.
// 왼쪽에서 오른쪽으로 순차적으로 삽입
// 삽입 이후에 루트노드까지 올라가며 정렬됨

struct PriorityQueue {
	int heap[MAX_SIZE];
	int count;
	
};

void swap(int *A, int *B) {
	int temp = *A;
	*A = *B;
	*B = temp;
}

void push(PriorityQueue* pq, int data) {
	if (pq->count >= MAX_SIZE) return;
	pq->heap[pq->count] = data;
	int now = pq->count; //완전 이진트리이므로 현재 count에 넣으면 가장 마지막 인덱스에 들어감
	int parent = ( pq->count - 1 ) / 2;  //트리에서 parent의 인덱스 공식
	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; //트리는 이미 정렬된 상태이고 이는 부모보다 더 큰 자식이 없다는 것을 의미. right와 left를 비교해서 둘다 root보다 작으면 더 찾을 필요 없음
		else {
			swap(&pq->heap[now], &pq->heap[target]);
			now = target;
			leftchild = now * 2 + 1;
			rightchild = now * 2 + 2; //부모 인덱스 찾는것 반대로
		}
	}

	return res;
}

int main()
{
	int n, data;
	cin >> n;
	PriorityQueue pq;
	pq.count = 0;
	for (int i = 0; i < n; i++) {
		cin >> data;
		push(&pq, data);
	}

	for (int i = 0; i < n; i++) {
		int data = pop(&pq);
		cout << data << " ";
	}
	return 0;
}

 

 

실행결과

 

pop함수에서 while문의 조건을 leftchild로 설정한 이유는 완전이진트리의 특성을 살려 '자식이 존재할때까지' 반복을 수행하게 하기 위함이다. Queue 내에서 항상 정렬상태를 부모,자식간의 정렬상태를 유지하기 위해 pop과 push 의 수행에 정렬과정이 진행되어야 한다.