[c++/자료구조] 정리: 우선순위 큐와 힙 (priority queue & heap)

1.우선순위 큐

큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다.

우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.

 

우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다.

힙(Heap)은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조이다.

• 최대 힙 (Max Heap)❝ key(부모노드) ≥ key(자식노드) ❞
• 부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리이다.

 

• 최소 힙 (Min Heap)❝ key(부모노드) ≥ key(자식노드) ❞
• 부모 노드의 키 값이 자식 노드보다 작거나 같은 완전이진트리이다.

2.우선순위 큐 구현방법 비교

삽입 또는 삭제 연산을 위한 힙의 시간복잡도는 O(log n).

---

3. 우선순위 큐 ADT

객체

• 우선순위를 가진 요소들의 모음

연산

• insert(x) : 우선순위 큐에 요소 x 추가
• remove() : 우선순위 큐에서 가장 우선순위가 높은 요소를 삭제하고 반환
• find() : 우선순위 큐에서 가장 우선순위가 높은 요소를 반환

 

4. 우선순위 큐 구현(c++)

#include <iostream>
using namespace std;

#define MAX_ELEMENT 200 //heap array size
template <typename T>
struct Node {
private:
	int key;
	T data;
public:
	Node() {
		key = 0;
	}
	Node(int ke, T da) {
		key = ke;
		data = da;
	}
	~Node(){}

	//getter/setter
	int getKey() {
		return key;
	}
	void setKey(int ke) {
		key = ke;
	}
	T getData() {
		return data;
	}
	void setData(T da) {
		data = da;
	}
};
template <typename T>
class maxHeap {
private:
	Node<T> node[MAX_ELEMENT];
	int size; //heap 요소 개수
public:
	maxHeap() {
		size = 0;
	}
	~maxHeap(){}

	//search node
	Node<T>& getParent(int index) {
		return node[index / 2];
	}
	Node<T>& getLeftChild(int index) {
		return node[index * 2];
	}
	Node<T>& getRightChild(int index) {
		return node[index * 2 + 1];
	}

	//삽입
	void insert(int key, T data) {
		if (isFull()) {
			cout << "heap is full" << endl;
			return;
		}
		int index = ++size; //힙트리 마지막 노드의 다음 위치에서 시작

		//힙트리를 거슬러 올라가며  부모 노드와 비교
		while (index != 1 && key > getParent(index).getKey()) {
			node[index] = getParent(index);
			index /= 2;
		}
		// 최종 위치에 데이터 삽입
		node[index].setKey(key);
		node[index].setData(data);
	}

	T remove() {
		if (isEmpty()) {
			cout << "Heap is Empty" << endl;
			exit(EXIT_FAILURE);
		}

		Node<T> itemNode = node[1];         // root node (삭제 대상)
		Node<T> lastNode = node[size--];    // 힙트리의 마지막 노드
		int index = 1;                      // 마지막 노드의 index (root 부터 시작)

		// root 부터 내려가며 자식 노드와 비교
		while (index <= size) {
			if (index * 2 > size) {//잎 노드인 경우 (자식 노드가 없는 경우)
				break;
			}
			else if (index * 2 == size) {//자식 노드가 하나인 경우
				if (lastNode.getKey() < getLeftChild(index).getKey()) {
					node[index] = getLeftChild(index);
					index *= 2;
				}
				else
				{
					break;
				}
			}
			else {//자식 노드가 두 개인 경우
				int leftChildKey = getLeftChild(index).getKey();
				int rightChildKey = getRightChild(index).getKey();

				//둘 중 key가 더 큰 자식 노드와 교환
				if (lastNode.getKey() < leftChildKey || lastNode.getKey() < rightChildKey) {
					node[index] = leftChildKey > rightChildKey ? getLeftChild(index) : getRightChild(index);
					index = leftChildKey > rightChildKey ? index * 2 : index * 2 + 1;
				}
				else {
					break;
				}

			}
		}
		node[index] = lastNode;     // 마지막 노드를 최종 위치에 저장
		return itemNode.getData();  // 삭제 노드의 data 반환
	}

	void display() {
		int level = 1;
		for (int i = 1; i <= size; i++) {
			if (i == level) {
				cout << endl;
				level *= 2;
			}
			cout << node[i].getData() << "(" << node[i].getKey() << ")  ";
		}
		cout << '\n' << "-------------------------" << endl;
	}

	bool isEmpty() {
		return size == 0;
	}
	bool isFull() {
		return size == MAX_ELEMENT - 1;
	}

};

int main() {
	maxHeap<int> priorityQueue;

	// 삽입
	priorityQueue.insert(10, 10);
	priorityQueue.insert(5, 5);
	priorityQueue.insert(30, 30);
	priorityQueue.insert(8, 8);
	priorityQueue.insert(9, 9);
	priorityQueue.insert(3, 3);
	priorityQueue.insert(7, 7);
	priorityQueue.display();

	// 삭제
	priorityQueue.remove();
	priorityQueue.display();
	priorityQueue.remove();
	priorityQueue.display();

	return 0;
}