(C++) 자료구조 - 우선순위 큐(Priority Queue) - 힙(Heap) - 배열(Array)

안녕하세요.

오늘은 자료구조 우선순위 큐(Priority Queue)에 대해서 알아보도록 하겠습니다!

 

1. 우선순위 큐(Priority Queue)와 큐(Queue) 구분?

우선순위 큐와 큐!  이름이 비슷한 두개부터 살펴보도록 하겠습니다.

큐는 먼저 들어간 데이터가 먼저 나오는 자료구조 형태

우선순위 큐는 우선순위가 높은 데이터가 먼저 나오는 자료구조 형태

우선 순위 큐는 들어간 순서에 상관없이 이름 그대로 우선 순위가 높은 데이터가 나오는 형태 입니다.

넓게 봤을 때 큐와 스택도 우선순위 큐로 생각 할 수 있습니다.

큐에서 우선순위는 먼저 들어간 데이터

스택에서 우선 순위는 나중에 들어간 데이터 라고 할 수 있으니까요.

(C++) 자료구조 - 큐(Queue) - 배열(Array), 링크드리스트(Linked List)

 

2. 우선순위 큐(Priority Queue)와 힙(Heap) 구분?

 

우선순위 큐 와 힙을 동일한 것이라고 생각하는 사람이 있을 수 있다고 생각하는데

엄밀히 말하면 둘은 다른 것입니다!

정의를 내려보자면 다음과 같습니다.

우선순위 큐는 우선순위가 높은 데이터가 먼저 나오는 자료구조 형태

힙은 완전 이진트리 형태이며 자식노드의 값보다 부모노드의 값이 크거나 같은 자료구조 형태

 

그런데 위에 힙의 정의에서 값을 우선순위이라 한다면

가장위에 있는 부모인 루트노드가 우선순위가 가장 높은 데이터를 가지게되고

데이터를 출력할때 루트노드를 가져온다면 우선순위 큐가 되기 때문에 

 힙의 구현은 우선순위 큐의 구현이 된다고 볼 수 있습니다.

엄밀히 말하면 둘은 다르지만 힙의 구현이 우선순위 큐의 구현이 된다고 말씀 드릴수 있네요!

 

물론 우선순위 큐를 힙의 형태로 구현하지 않을 수도 있습니다!

배열이나 리스트로 구현한 뒤 비교연산을 통해 우선순위가 가장 높은 값을 찾고

그 값을 가져오면 되는 거니까요!

혹은 빼내기 쉽게 정렬해놓은 다음 첫번째 인덱스를 반환하는 것도 한 방법입니다.

다만 배열,리스트로 구현했을때 삽입과 삭제, 데이터 비교연산, 정렬하는데 연산이 데이터가 늘어나면 늘어날수록

힙으로 구현했을 때와 비용차이가 많이 나기 때문에 많은 사람들이 우선순위 큐를 힙으로 구현하고 있습니다!

(C++) 자료구조 - 이진트리(Binary Tree) - 링크드리스트(Linked List)

3. 힙을 이용한 우선순위 큐 구현

힙 구현이 우선순위 큐의 구현과 다르지 않다고 했기 때문에 

힙을 잘 구현하기만 하면 됩니다.

자 그러면 힙은 어떤 형태로 구현할까요?!

힙은 보통 배열 형태로 구현하게 됩니다.

이진 트리 형태는 리스트로 구현했으면서 힙은 배열이라구요?! 하실 수 있는데요

힙의 형태인 완전 이진트리는 위에서부터 차곡차곡, 왼쪽부터 오른쪽으로 값이 들어가게 되는데

이는 저번 이진트리 구현에서 말했던 메모리 공간 낭비가 없다는 뜻을 뜻하고

배열 특성상 다음 데이터의 삽입 위치를 바로 알수 있습니다.

그리고 리스트 형태로 구현한다면 마지막 위치를 알아내기가 어렵죠.

배열로 구현을 하면 간단히 해결되는 문제이기에 힙은 배열로 구현하는게 정석이 되어버렸다고 보셔도 될거 같습니다.

 

 

3 - 1 배열을 이용한 힙 (을 이용한 우선순위 큐)구현

 

힙을 배열로 구현 할건데요!

배열로 구현하면 자식은 어떻게 어떻게 구분하냐! 라고 하실 수 있어

설명을 드리도록 하겠습니다.

완전 이진트리는 초록색 숫자대로 노드가 생성 되는 것을 알고 계실겁니다.

그대로 배열 인덱스를 적용할건데요

자세히 살펴보시면 규칙을 발견 하실 수 있습니다.

자식 노드 인덱스 값의 / 2 는 부모노드의 인덱스 값이 됩니다. (소수점은 버림)

 왼쪽 자식노드 인덱스는 부모노드 * 2

오른쪽 자식노드 인덱스는 부모노드 * 2 + 1

이렇게 해서 자식, 부모노드를 알 수 있게 되었습니다.

또한 가독성과 편의를 위해서 배열 0번째는 사용하지 않았습니다!

struct Heapdata
{
	int priority;		//우선 순위 값
	int data;		//데이터 값
};

class HeapArray
{
private:
	int heapIndex;
	int maxSize;
	Heapdata* heapArray;

	bool GetParentIndex(int index, int& returnindex);
	bool GetLeftChildIndex(int index, int& indreturnindexex);
	bool GetRightChildIndex(int index, int& returnindex);
	bool GetPriorityChildIndex(int index, int& returnindex);	//우선순위 높은 자식인덱스 반환

public:
	HeapArray(int size = 10);
	~HeapArray();

	bool Insert(int priority, int data);
	bool Delete(int& data);
	void PrintAll();
};

배열 힙의 헤더입니다.

 

Get 관련 함수는 Heap 내부에서 사용하기 때문에 private 로 넣어두었고

Insert 와 Delete 가 우선순위 큐에서 Enqueue Dequeue 역할을 한다고 보시면 됩니다.

그렇기 때문에 heap 을 우선순위 큐로 감싸는 작업은 하지 않을게요!

#include "HeapArray.h"
#include <iostream>

HeapArray::HeapArray(int size)
{
	heapIndex = 0;
	maxSize = size;
	heapArray = new Heapdata[maxSize + 1];

	printf("생성자\n");
}

HeapArray::~HeapArray()
{
	printf("소멸자\n");
}

bool HeapArray::Insert(int priority, int data)
{
	if (heapIndex >= maxSize)
		return false;

	Heapdata newData = { priority ,data };
	int parentIndex;
	int currentIndex = heapIndex + 1;

	while (GetParentIndex(currentIndex, parentIndex))
	{
		if (newData.priority < heapArray[parentIndex].priority)
		{
			heapArray[currentIndex] = heapArray[parentIndex];
			currentIndex = parentIndex;
		}
		else
			break;
	}
	heapArray[currentIndex] = newData;
	heapIndex++;
	return true;
}

bool HeapArray::Delete(int& data)
{
	if (heapIndex <= 0)
		return false;

	data = heapArray[1].data;
	printf("Delete - data : %d\n", data);

	Heapdata lastData = heapArray[heapIndex];
	int parentIndex = 1;
	int childIndex;

	while (GetPriorityChildIndex(parentIndex, childIndex))
	{
		if (lastData.priority <= heapArray[childIndex].priority)
			break;

		heapArray[parentIndex] = heapArray[childIndex];
		parentIndex = childIndex;
	}

	heapArray[parentIndex] = lastData;
	heapIndex--;

	return true;
}

bool HeapArray::GetParentIndex(int index, int& returnindex)
{
	if (index / 2 == 0)
		return false;

	returnindex = index / 2;
	return true;
}

bool HeapArray::GetLeftChildIndex(int index, int& returnindex)
{
	if (index * 2 > heapIndex)
		return false;

	returnindex = index * 2;
	return true;
}

bool HeapArray::GetRightChildIndex(int index, int& returnindex)
{
	if (index * 2 + 1 > heapIndex)
		return false;

	returnindex = index * 2 + 1;
	return true;
}

bool HeapArray::GetPriorityChildIndex(int index, int& returnindex)
{
	int left;
	int right;
	if (GetLeftChildIndex(index, left) && GetRightChildIndex(index, right)) //자식이 2개 일경우
	{
		returnindex = heapArray[left].priority <= heapArray[right].priority ? left : right;
		return true;
	}
	else if (GetLeftChildIndex(index, left)) //왼쪽 자식만 있을경우
	{
		returnindex = left;
		return true;
	}
	else		//자식이 없는 단말 노드일 경우
		return false;

}

void HeapArray::PrintAll()
{
	for (int i = 1; i <= heapIndex; i++)
	{
		printf("index : %d    pri : %d    data : %d\n", i, heapArray[i].priority, heapArray[i].data);
	}
}

배열 힙의 CPP 입니다.

 

위에서 간단히 설명한 Get 함수는 건너뛰고

Insert 함수, Delete 함수, GetPriorityChildIndex 함수 만 살펴보도록 하겠습니다.

 

먼저 GetPriorityChildIndex 함수입니다.

각 if 문 순서대로

1. 자식 노드가 2개 있으면 우선순위 높은 자식의 인덱스 반환

2. 자식 노드가 1개 있으면 (완전 이진트리이니 왼쪽 자식이겠죠?) 왼쪽 자식 인덱스 반환

3. 둘다 없으면 false 반환

입니다.

우선 순위는 더 낮은 값일수록 우선순위가 높다고 하였습니다!

 

다음은 Insert 함수 입니다.

마지막 위치에 생성된 새로운 노드와 부모노드의 우선순위를 비교하여

자기 자리를 찾아가는 연산을 하고 있습니다.

아래서부터 올라가는 연산을 하는 것이지요.

 

Delete 함수입니다.

루트 노드가 빠지고

그 자리를 맨 마지막 노드가 채웠다고 보시면 됩니다.

맨 마지막 노드와 자식 노드 중 우선순위가 높은 자식과 비교하여

자리를 스왑하면서 자기 자리를 찾아가게 됩니다.

Insert 와는 다르게 아래로 내려가는 연산을 한다고 보시면 되겠습니다.

#include <iostream>
#include "HeapArray.h"

int main()
{
	HeapArray* arrayHeap = new HeapArray();

	arrayHeap->Insert(9, 9);
	arrayHeap->Insert(1, 1);
	arrayHeap->Insert(8, 8);
	arrayHeap->Insert(3, 3);
	arrayHeap->Insert(5, 5);
	arrayHeap->Insert(4, 4);
	arrayHeap->Insert(1, 10);
	arrayHeap->Insert(6, 6);
	arrayHeap->Insert(7, 7);
	arrayHeap->Insert(2, 2);
	arrayHeap->PrintAll();

	printf("\n");
	int data;
	arrayHeap->Delete(data);
	arrayHeap->Delete(data);
	arrayHeap->Delete(data);
	arrayHeap->Delete(data);
	arrayHeap->Delete(data);
	arrayHeap->Delete(data);
	arrayHeap->Delete(data);
	arrayHeap->Delete(data);
	arrayHeap->Delete(data);
	arrayHeap->Delete(data);
	arrayHeap->Delete(data);
	arrayHeap->Delete(data);
	arrayHeap->PrintAll();

	delete arrayHeap;
}

결과를 보시면 부모노드는 자식 노드 보다 우선 순위가 높고

Delete 를 했을 때 우선 순위가 높은 순서대로 Delete 되는 것을 볼 수 있습니다.

1 과 10 은 우선 순위가 동일하고 그에 맞게 출력 되고 있네요!

감사합니다.

 

다른 자료구조

단일 연결 리스트(Singly Linked List)

이중 연결 리스트(Doubly Linked List)

스택(Stack) - 배열(Array), 링크드리스트(Linked List)

큐(Queue) - 배열(Array), 링크드리스트(Linked List)

이진트리(Binary Tree) - 링크드리스트(Linked List)

이진트리(Binary Tree) - 링크드리스트(Linked List)

우선순위 큐(Priority Queue) - 힙(Heap) - 배열(Array)