우선순위 큐(Priority Queue)와 힙(Heap) - 9장

우선순위 큐

간단하게 말해서 "들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다"

 

이 우선순위의 판단 근거는 프로그래머가 결정할 일이다. 즉 목적에 맞게 우선순위를 결정하면 된다.

따로 우선순위정보를 넣어줄 수 있고, 저장할 데이터를 근거로 우선순위를 판단할 수 있다.(ex 사전순서)

 

우선순위 큐를 구현하는 방법은 여러가지가 될 수 있지만

 

순수 배열을 통한 구현을 할 시 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야한다.

그리고 삽입의 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야할 수 있다.

-> 이 문제점은 연결리스트도 마찬가지.

 

그렇기에 우선순위 큐를 구현한다고 하면 '힙(heap)'이라는 자료구조를 이용해 구현하는 것이 일반적이다.

 

힙의 소개

힙은 '이진 트리'이면서 '완전 이진 트리'이다. 

힙은 이 완전 이진 트리를 배열을 통해 구현하는데 이는 완전 이진 트리의 규칙(위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡)을 통한 특별한 규칙을 이용하여 접근 속도가 매우 빠르다.

참고로 힙의 삽입/삭제/탐색의 시간은 최악의 경우에도 O(logN)이 보장이 된다.

 

힙은 크게 두 종류가 존재하는데 다음과 같다.

최대 힙

- 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리를 가리켜 '최대 힙'이라 한다.

 

최소 힙

- 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리를 가리켜 '최소 힙'이라 한다.

 

힙은 우선순위 큐와 동일하게 인식하는 경향이 매우 강한데, 비슷하지만 이는 개념상으로는 다른것이다.

 

힙에서의 데이터 저장과정

최소 힙을 기준으로 설명한다.

 

위 그림에서 3을 저장하는 과정인데 그 과정을 보면 맨 먼저 완전 이진 트리의 노드가 들어오는 순서를 생각하면

15다음에 3이 들어와야한다. 이 3은 최소 힙의 기준에서 부모인 8보다 우선순위가 낮기때문에 위로 올라가고, 또 올라가면서 부모인 4와 비교하면서 자리를 교체한다. 그런다음 1과 비교해보니 나보다 우선순위가 높고 그 자리에 안착한다.

(실제 구현할때는 매번 위치를 바꾸진 않고, 자리를 찾은 다음 그 자리에 위치한 노드와 자리를 바꾼다.)

 

이렇듯 데이터의 추가과정은 마지막 위치에 데이터를 두고서 부모 노드와의 비교를 통해 자신의 위치를 찾아가는

매우 단순한 방식

 

힙에서의 데이터 삭제과정

힙에서의 삭제는 삽입과는 반대로 이루어진다고 생각하면 편하다.

 

우선 삭제. 무엇을 삭제해야할까? 우리는 우선순위 큐의 구현을 위해서 힙을 활용한다.

우선순위 큐는 '가장 높은 우선순위의 데이터 삭제'를 의미하므로,

최상위 노드인 루트 노드가 우선순위가 가장 높으므로 그 녀석을 제거하는게 옳은 접근 방식이다.

 

힙에서 루트 노드를 제거하는 간단한 단계를 보자.

1. 루트 노드를 제거한다.

2. 루트 노드의 빈칸을 채우기 위해 맨 마지막 노드(완전 이진 트리에서)를 루트 노드로 옮긴다.

3. 당연히 맨 마지막 노드는 우선순위가 가장 낮아야 하기에 자식노드와 비교하면서 다시 내려간다(자리를 찾아간다)

 

제자리를 찾아간다는 점에선 삽입과 유사한 방식이다. 

 

루트노드는 1이었다.

1을 제거하고, 맨 마지막 노드를 루트로 옮긴다음 자기자리를 찾아가고 있다.

 

참고로 맨 마지막 노드가 루트노드로 옮겨가고, 자식 노드 둘다 나보다 우선순위가 높은데.

이럴때는 어떻게 판단을 할까.

 

간단하다. 자식 노드중 우선순위가 더 높은 녀석을 따라가면 되는 것이다. (결국 우선순위가 높은녀석과 바꿔야하므로)

 

이와같이 힙에서의 삽입/삭제 과정에서 보인 성능을 평가해보면

완전 이진 트리의 레벨에서 비교연산이 한번씩 이루어진다. 즉 전체 데이터가 1024개라고 가정하면

1024개의 트리의 높이는 10밖에 되지 않으므로 데이터가 1024개이고 제자리를 찾아가는 결과가 맨 마지막이라 할지라도 최대 10번만 연산하면 되는것이다. (logN의 시간복잡도)

 

이렇기에 우선순위 큐를 배열이나 연결 리스트를 기반으로 구현하는것보다 훨씬 더 좋은 결과와 성능을 보인다.

 

배열을 기반으로 힙을 구현

힙은 완전 이진 트리이다. 배열을 사용한다고 해서 배열 그자체가 아니란 소리.

즉 배열을 통해 완전 이진 트리를 표현하는 것. ★

 

그것이 가능한 이유가 완전 이진 트리는 위에서 아래로 왼쪽에서 오른쪽으로 순서대로 저장된다는 규칙을 떠올려보면

노드에 숫자를 1부터 노드의 수 만큼 가리킬 수 있다는 의미이다.

 

이렇게. 노드에 달린 숫자는 배열의 인덱스 번호에 대입을 하면 그것을 통해 배열을 완전 이진 트리로 표현할 수 있다.

 

그럼 왼쪽 자식노드와 오른쪽 자식노드의 인덱스 값은 어떻게 얻어올까? 간단하다.

 

왼쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스값 * 2

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

부모 노드의 인덱스 값 : 자식 노드의 인덱스 값 / 2 (왼쪽이든 오른쪽이든 / 2를 하면 정수값을 얻어오기에 가능한 것)

 

이제 이론에 관한 설명은 마쳤고 힙을 구현해본다.

#pragma once

class HeapNode // char형 데이터를 담는다.
{
public:
	HeapNode();
	HeapNode(int priority, char data);
	int GetPriority() const;
	char GetData() const;
private:
	int m_priority;
	char m_data;
};

class Heap
{
public:
	Heap();
	~Heap();
	int GetParentIdx(int idx) const ; // 부모노드 인덱스 값 반환
	int GetLeftChildIdx(int idx) const; // 왼쪽자식노드 인덱스 값 반환
	int GetRightChildIdx(int idx) const; // 오른쪽 자식노드 인덱스 값 반환
	int GetHighPriChildIdx(int idx); // 우선순위 비교 함수.
	bool IsEmpty() const;
	void Insert(int priority, char data);
	char Delete();
private:
	enum { MAX = 100 };
	int m_numOfData;
	HeapNode* m_heapArr;
};

cpp코드

#include "Heap.h"
HeapNode::HeapNode() : m_priority(0), m_data(0)
{

}
HeapNode::HeapNode(int priority, char data) : m_priority(priority), m_data(data)
{

}
int HeapNode::GetPriority() const
{
	return this->m_priority;
}
char HeapNode::GetData() const
{
	return this->m_data;
}

Heap::Heap() : m_numOfData(0), m_heapArr(new HeapNode[MAX])
{

}

Heap::~Heap()
{
	delete[] m_heapArr;
}

int Heap::GetParentIdx(int idx) const
{
	return idx / 2;
}

int Heap::GetLeftChildIdx(int idx) const
{
	return idx * 2;
}
int Heap::GetRightChildIdx(int idx) const
{
	return idx * 2 + 1;
}

bool Heap::IsEmpty() const
{
	return m_numOfData == 0 ? true : false;
}
int Heap::GetHighPriChildIdx(int idx) // 자식노드중 우선순위가 높은 녀석을 반환.
{
	// 자식노드가 없는 경우. (단말노드등)
	if (GetLeftChildIdx(idx) > this->m_numOfData)
		return 0;
	else if (GetLeftChildIdx(idx) == this->m_numOfData)
		return GetLeftChildIdx(idx); // 자식노드가 하나인 경우(왼쪽. 마지막 노드)
	else // 자식노드 둘 다 존재한다면. 이때부터 비교!
	{
		// 참고로 숫자가 적은게 우선순위가 위.
		if (m_heapArr[GetLeftChildIdx(idx)].GetPriority()
				 > m_heapArr[GetRightChildIdx(idx)].GetPriority())
			return GetRightChildIdx(idx); // 왼쪽자식노드가 우선순위가 더 높으면
		else
			return GetLeftChildIdx(idx);
	}


}

void Heap::Insert(int priority, char data) //삽입의 과정은 맨마지막에 넣고. 부모와 비교과정.
{
	int idx = m_numOfData + 1;
	HeapNode node(priority, data);

	while (idx != 1) // 힙의 노드가 하나인 경우가 아닐 때.
	{
		if (priority < m_heapArr[GetParentIdx(idx)].GetPriority())
		{ // 부모노드의 우선순위 순수값이 더 크다면 (우선순위가 낮음)
			m_heapArr[idx] = m_heapArr[GetParentIdx(idx)]; // 부모노드는 자식노드로 내려옴.
			idx = GetParentIdx(idx); // 부모 인덱스를 얻어옴.
		}
		else // 부모의 우선순위가 더 높은경우.
		{
			break;
		}
	}

	m_heapArr[idx] = node;
	++m_numOfData;
}

char Heap::Delete() // 삭제의 과정은 루트노드 뽑고 마지막노드 올라오면서 자기자리 찾기.
{
	
	char retData = m_heapArr[1].GetData(); // 루트노드
	HeapNode node(m_heapArr[m_numOfData]); // 얕은복사. 마지막노드

	int parentIdx = 1,childIdx;

	while (childIdx = GetHighPriChildIdx(parentIdx))
	{
		// 나보다 우선순위가 낮은녀석을 만날 때까지.
		if (m_heapArr[childIdx].GetPriority() > node.GetPriority())
			break;
		m_heapArr[parentIdx] = m_heapArr[childIdx]; // 우선순위가 높은 자식은 부모로 저장.
		parentIdx = childIdx;
	}
	m_heapArr[parentIdx] = node;// 마지막에 자기 자리저장.
	--m_numOfData;
	return retData;
}

 

하지만 조금 아쉬운점은 우선순위의 기준을 코드에서 직접 결정하는게 아닌 우리가 넣어주고 있다는 점.

 

이제 우리가 우선순위의 판단 기준을 힙에 설정해본다.

#pragma once

typedef int (PriorityComp)(char op1, char op2);

class Heap
{
public:
	Heap() = delete;
	Heap(PriorityComp pc);
	~Heap();
	int GetParentIdx(int idx) const ; 
	int GetLeftChildIdx(int idx) const; 
	int GetRightChildIdx(int idx) const; 
	int GetHighPriChildIdx(int idx); 
	bool IsEmpty() const;
	void Insert(char data); // 더이상 우선순위를 매번 넘길필요가 없어졌다!
	char Delete();
private:
	enum { MAX = 100 };
	PriorityComp* cmp; // 함수 포인터
	int m_numOfData;
	char* m_heapArr; // 이제 노드를 담는게 아닌 데이터만!
};

HeapNode를 제거하고, 순수히 우선순위의 판단은 힙노드 클래스를 통해서가 아닌 작성자가 따로 결정한 기준을 통해서!

 

typedef int (PriorityComp)(char op1, char op2);
PriorityComp* cmp; // 함수 포인터

책의 함수 포인터의 기준은 다음과 같다.

 

1. 첫 번째 인자의 우선순위가 높다면 0보다 큰 값이 반환되도록 정의한다.

2. 두 번째 인자의 우선순위가 높다면, 0보다 작은 값이 반환되도록 정의한다.

3. 첫 번째, 두 번째 인자의 우선순위가 동일하다면 0이 반환되도록 정의한다.

 

등록할 함수는

int dataPriorityComp(char ch1, char ch2)
{
	return ch2 - ch1;
}

우리는 간단하게 '문자'만 저장하므로. 아스키코드 값의 비교이다.

즉  두번째가 더 크다면 음수의 값이 나와 오른쪽의 우선순위가 더 크단 이야기이며,

양수가 나온다면 ch1의 문자의 우선순위가 높다.

동일할 시 0.

 

수정된 cpp코드

#include "Heap.h"


Heap::Heap(PriorityComp pc) : m_numOfData(0), m_heapArr(new char[MAX]), cmp(pc)
{

}

Heap::~Heap()
{
	delete[] m_heapArr;
}

int Heap::GetParentIdx(int idx) const
{
	return idx / 2;
}

int Heap::GetLeftChildIdx(int idx) const
{
	return idx * 2;
}
int Heap::GetRightChildIdx(int idx) const
{
	return idx * 2 + 1;
}

bool Heap::IsEmpty() const
{
	return m_numOfData == 0 ? true : false;
}
int Heap::GetHighPriChildIdx(int idx) // 자식노드중 우선순위가 높은 녀석을 반환.
{
	// 자식노드가 없는 경우. (단말노드등)
	if (GetLeftChildIdx(idx) > this->m_numOfData)
		return 0;
	else if (GetLeftChildIdx(idx) == this->m_numOfData)
		return GetLeftChildIdx(idx); // 자식노드가 하나인 경우(왼쪽. 마지막 노드)
	else // 자식노드 둘 다 존재한다면. 이때부터 비교!
	{
		// 변경. 이제는 왼쪽자식노드와 오른쪽자식노드간의 비교를 우선순위 함수에게 넘김.
		// 0보다 크면 왼쪽자식노드. 작으면 오른쪽 자식노드 반환.
		if ((*cmp)(m_heapArr[GetLeftChildIdx(idx)], m_heapArr[GetRightChildIdx(idx)]) < 0)
			return GetRightChildIdx(idx);
		else
			return GetLeftChildIdx(idx);
	}


}

void Heap::Insert(char data) //삽입의 과정은 맨마지막에 넣고. 부모와 비교과정.
{
	int idx = m_numOfData + 1;
	

	while (idx != 1) // 힙의 노드가 하나인 경우가 아닐 때.
	{
		if ((*cmp)(data, m_heapArr[GetParentIdx(idx)]) > 0)
		{
			// 첫번째 인자가 우선순위가 높다면. 즉 들어온 노드가 부모노드보다 우선순위가 높음
			m_heapArr[idx] = m_heapArr[GetParentIdx(idx)];
			idx = GetParentIdx(idx);
		}
		else // 부모의 우선순위가 더 높은경우.
		{
			break;
		}
	}

	m_heapArr[idx] = data;
	++m_numOfData;
}

char Heap::Delete() // 삭제의 과정은 루트노드 뽑고 마지막노드 올라오면서 자기자리 찾기.
{
	
	char retData = m_heapArr[1]; // 루트노드
	char lastElem = m_heapArr[m_numOfData];
	int parentIdx = 1,childIdx;

	while (childIdx = GetHighPriChildIdx(parentIdx))
	{
		// 나보다 우선순위가 낮은녀석을 만날 때까지.
		if ((*cmp)(m_heapArr[childIdx], lastElem) <= 0)
			break;
		m_heapArr[parentIdx] = m_heapArr[childIdx]; // 우선순위가 높은 자식은 부모로 저장.
		parentIdx = childIdx;
	}
	m_heapArr[parentIdx] = lastElem;
	--m_numOfData;
	return retData;
}

 

 

결과.

int main()
{
	Heap hp(dataPriorityComp);

	for (int i = 0; i < 10; ++i)
	{
		hp.Insert('A' + i);
	}

	while (!hp.IsEmpty())
	{
		cout << hp.Delete() << endl;
	}
	
	return 0;
}