9. 우선순위 큐와 힙

1. 우선순위 큐의 이해

 

▣ 우선순위 큐와 우선순위의 이해

1. 큐의 핵심 연산

· enqueue :  쿠에 데이터를 삽입하는 행위
· dequeue :  큐에 데이터를 꺼내는 행위

 

2. 우선운위 큐의 핵심 연산

· enqueue :  큐에 데이터를 삽입하는 행위
· dequeue : 큐에 데이터를 꺼내는 행위

※ 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다

 

 

▣ 우선순위 큐의 구현방법

· 배열을 기반으로 구현하는 방법
· 연결리스트를 기반으로 구현하는 방법
· 힙을 이용하는 방법

두 가지 방법 모두 최악의 경우 새 데이터의 위치를 찾기 위해서 
기존에 저장된 모든 데이터와 비교를 진행해야 한다. 

 

※ 우선순위큐는 우선순위를 근거로 적정 위치를 찾아서 데이터를 저장하는 방식이다

 

▣ 힙의 소개

최대힙

모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다.  
루트 노드에 저장된 값이 가장 커야 한다. 

 

 

최소힙

모든 노드에 저장된 값은 자식 노드에 저장된 값보다 작거나 같아야 한다.  
루트 노드에 저장된 값이 가장 작아야 한다. 

 

---

2. 힙의 구현과 우선순위 큐의 완성

 

 

▣ 힙에서의 데이터 저장과정

 

1. 자식 노드 데이터의 우선순위 ≤ 부모 노드 데이터의 우선순위 (최소힙?)

 

2. 새 데이터는 우선순위가 낮다는 가정하에 끝!
 에 저장 그리고 부모 노드와 비교를 진행

3. 부모 노드와 비교 및 자리 바꿈 

 

4. 자리를 찾는다

 

▣ 삽입과 삭제의 과정에서 보인 성능의 평가 (우선순위 큐의 시간 복잡도 )

 

∙ 배열 기반 데이터 삽입의 시간 복잡도   O(n) 
∙ 배열 기반 데이터 삭제의 시간 복잡도   O(1)
 

∙ 연결 리스트 기반 데이터 삽입의 시간 복잡도   O(n) 
∙ 연결 리스트 기반 데이터 삭제의 시간 복잡도   O(1)
 

∙ 힙 기반 데이터 삽입의 시간 복잡도   O(log 2 n) 
∙ 힙 기반 데이터 삭제의 시간 복잡도   O(log 2 n)
 

▣ 배열을 기반으로 힙을 구현하는데 필요한 지식들 

“연결 리스트를 기반으로 힙을 구현하면, 새로운 노드를 힙의 마지막 위치‟
에 추가하는 것이 쉽지 않다.”   

 

 

∙ 왼쪽 자식 노드의 인덱스 값     =>  부모 노드의 인덱스 값 * 2 
∙ 오른쪽 자식 노드의 인덱스 값  =>  부모 노드의 인덱스 값 * 2 + 1 
∙ 부모 노드의 인덱스 값            => 자식 노드의 인덱스 값 / 2 

▣ 힙 구현: 숙지할 내용 


∙ 힙은 완전 이진 트리이다. 
∙ 힙의 구현은 배열을 기반으로 하며 인덱스가 0인 요소는 비워둔다. 
∙ 따라서 힙에 저장된 노드의 개수와 마지막 노드의 고유번호는 일치한다. 
∙ 노드의 고유번호가 노드가 저장되는 배열의 인덱스 값이 된다. 
∙ 우선순위를 나타내는 정수 값이 작을수록 높은 우선순위를 나타낸다고 가정한다 

※ 배열을 기반으로 하는 경우! 힙에 저장된 노드의 개수와 지막 노드의 고유번호가 일치하기 때문에 
    마지막 노드의 인덱스 값을 쉽게 얻을 수 있다! 

▣ 힙 구현 : 구조체

typedef struct _heapElem 
{
	Priority pr;   // 값이 작을수록 높은 우선순위     
	HData data; 
} HeapElem; 

typedef struct _heap 
{ 
	int numOfData;     
	HeapElem heapArr[HEAP_LEN]; 
} Heap;

▣ 힙 구현: 초기화와 Helper 

void HeapInit(Heap* ph)
{
	ph->numOfData = 0;
}

int HIsEmpty(Heap* ph)
{
	if (ph->numOfData == 0)
		return true;
	else
		return false;
}

int GetParentIndex(int idx)
{
	return idx / 2;
}

int GetLChildIndex(int idx)
{
	return idx * 2;
}

int GetRChildIndex(int idx)
{
	return GetLChildIndex(idx) +1;
}

//두 개의 자식 노드 중 높은 우선순위의 자식 노드 인덱스 값 반환
int GetHipriChildIDX(Heap * ph, int idx)
{
	//자식 노드가 존재하지 않는다면,  
	//numOfData는 마지막 노드의 고유번호이니,
	//자식 노드의 값이 이보다 크면 존재하지 않는 자식 노드이다. 
	if (GetLChildIndex(idx > ph->numOfData))
	{
		return 0;
	}
	
	//자식 노드가 왼쪽 자식 노드 하나만 존재한다면, 
	//자식 노드가 하나 존재하면 이는 왼쪽 자식 노드이다. 완전 이진 트리 이므로
	else if (GetLChildIndex(idx == ph->numOfData))
	{
		return GetLChildIndex(idx);
	}

	//자식 노드가 둘다 존재한다면, 
	else
	{
		//오른쪽 자식 노드의 우선순위가 높다면
		if (ph->heapArr[GetLChildIndex(idx)].pr > ph->heapArr[GetRChildIndex(idx)].pr)
		{
			return GetRChildIndex(idx);   //오른쪽 자식 노드의 인덱스 값 반환
		}
		else
		{
			return GetLChildIndex(idx);   //왼쪽 자식 노드의 인덱스 값 반환
		}
	}
}

▣ 힙 구현 : HInsert

 

1. 힙의 마지막 자리에 새로운 노드를 배정 (실제로 넣지는 않고 가정만 한다.)
2. 그의 부모노드와 우선순위를 비교하여 위치 변경
3. 삭제의 과정이 위에서 밑으로 였다면, 삽입의 과정은 밑에서 위로

void HInsert(Heap * ph, HData data, Priority pr)
{
	int idx = ph->numOfData + 1;		//새 노드가 저장될 인덱스 값을 idx 저장
	HeapElem nelem = { pr, data };		//새 노드의 생성 및 초기화

	while (idx != 1)					//새노드가 루트노드까지 while
	{
		//새노드의 우선순위가 높다면
		if (pr < (ph->heapArr[GetParentIndex(idx)].pr))       
		{
			//부모 노드를 한레벨 내림, (실제로 내림)
			ph->heapArr[idx] = ph->heapArr[GetParentIndex(idx)];

			//새 노드를 한 레벨 올림, (실제로는 인덱스 값만 갱신)
			idx = GetParentIndex(idx);
		}
		else
			break;
	}
	ph->heapArr[idx] = nelem; //새 노드를 배열에 저장
	ph->numOfData += 1;       //총 데이터수 +1
}

▣ 힙 구현 : HDelete

1. 가장 마지막 노드를 추출한다. (그리고 마지막노드를 루트노드로 이동시키고 재정렬)
2. 인덱스 1번에 위치한 노드가 삭제되기 때문에 그 밑의 자식노드들과 마지막 노드의 우선순위를 비교한다.
3. 자식노드의 우선순위를 비교할 때, GetHiPriChildIDX() 함수를 사용한다.
4. 현재의 노드가 마지막 노드보다 우선순위가 높다면 한칸 위로 이동한다. (1번이 빠졌기 때문에 공간을 메운다.)
5. 마지막 노드보다 우선순위가 낮거나, 자식노드가 더이상 없을 때, 마지막 노드의 자리가 결정된다.

HData HDelete(Heap * ph)  
{
	HData retData = (ph->heapArr[1]).data;           //반환을 위해서 삭제할 데이터 저장
	HeapElem lastElem = ph->heapArr[ph->numOfData];   //힙의 <마지막 노드> 저장

	// 아래의 변수 parentIdx에는 마지막 노드가 저장될 위치정보가 담긴다.
	int parentIdx = 1;  //루트 노드가 위치해야할 인덱스 값 저장
	int childIdx;

	//루트 노드의 우선수위가 높은 자식 노드를 시작으로 반복문 시작
	while (childIdx = GetHipriChildIDX(ph, parentIdx))
	{
		if (lastElem.pr <= ph->heapArr[childIdx].pr)        //마지막 노드와 우선순위 비교
			break;                                          //마지막 노드의 우선순위가 높으면 반복문 탈출

		//마지막 노드보다 우선순위 높으니, 비교대상 노드의 위치를 한 레벨 올림
		ph->heapArr[parentIdx] = ph->heapArr[childIdx];
		parentIdx = childIdx;                               //마지막 노드가 저장될 위치정보를 한 레벨 내림
	}
	//반복문 탈출하면 parentIdx에는 마지막 노드의 위치정보가 저장됨
	ph->heapArr[parentIdx] = lastElem;           //마지막 노드 최종 저장
	ph->numOfData -= 1;
	return retData;
}

 

▣ 힙 구현 :  main

int main()
{
	Heap heap;
	HeapInit(&heap);

	HInsert(&heap, 'A', 1);
	HInsert(&heap, 'B', 2);
	HInsert(&heap, 'C', 3);
	cout << HDelete(&heap) << "\n";

	HInsert(&heap, 'A', 1);
	HInsert(&heap, 'B', 2);
	HInsert(&heap, 'C', 3);
	cout << HDelete(&heap) << "\n";

	while(!HIsEmpty(&heap))
		cout << HDelete(&heap) << "\n";

	return 0;
}

---

▣ 힙 구현 : 힙의 변경

데이터를 저장할 때 우선순위 정보를 별도로 전달하는 것은 적합하지 않은 경우가 많다. 
일반적으로  데이터의 우선순위는 데이터를 근거로 판단이 이뤄지기 때문이다.  

typedef int PriorityComp(HData d1, HData d2);

typedef struct _heap 
{ 
	PriorityComp * Comp;
	int numOfData;     
	HData heapArr[HEAP_LEN]; 
} Heap;

void HeapInit(Heap* ph, PriorityComp pc)
{
	ph->numOfData = 0;
	ph->Comp = pc;
}

 

▣ 힙 구현: PriorityComp

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

∙ 첫 번째 인자의 우선숚위가 높다면, 0보다 큰 값 반환  
 
∙ 두 번째 인자의 우선숚위가 높다면, 0보다 작은 값 반환
 
∙ 첫 번째, 두 번째 인자의 우선숚위가 동일하다면, 0이 반환

 

void HInsert(Heap * ph, HData data, Priority pr); //이 함수를

void HInsert(Heap * ph, HData data) //로 변경

 

※ PriorityComp형 함수가 등록되면 HInsert 함수는 등록된 함수를 활용하여 우선순위를 비교 판단한다

▣ 힙 구현 :  Helper 함수의 변경 

 

int GetHipriChildIDX(Heap * ph, int idx)
{
	if (GetLChildIndex(idx > ph->numOfData))
	{
		return 0;
	}
	else if (GetLChildIndex(idx == ph->numOfData))
	{
		return GetLChildIndex(idx);
	}
	else
	{
		if (ph->Comp( ph->heapArr[GetLChildIndex(idx)], 
						ph->heapArr[GetRChildIndex(idx)]) <0)
		{
			return GetRChildIndex(idx);   
		}
		else
		{
			return GetLChildIndex(idx);  
		}
	}
}

 

comp에 등록된 함수의 호출결과를  통해서 우선순위를 판단한다

 

▣ 힙 구현 :  HInsert의 변경 

 

void HInsert(Heap * ph, HData data)
{
	int idx = ph->numOfData + 1;		//새 노드가 저장될 인덱스 값을 idx 저장

	while (idx != 1)				
	{
		//새노드의 우선순위가 높다면
		if (ph->Comp (data , ph->heapArr[GetParentIndex(idx)]) >0)
		{
			ph->heapArr[idx] = ph->heapArr[GetParentIndex(idx)];

			idx = GetParentIndex(idx);
		}
		else
			break;
	}
	ph->heapArr[idx] = data; //새 노드를 배열에 저장
	ph->numOfData += 1;       //총 데이터수 +1
}

comp에 등록된 함수의 호출결과를   통해서 우선순위를 판단한다

 

▣ 힙 구현 :  HDelete의 변경 

HData HDelete(Heap * ph)  
{
	HData retData = ph->heapArr[1];           //반환을 위해서 삭제할 데이터 저장
	HData lastElem = ph->heapArr[ph->numOfData];   //힙의 <마지막 노드> 저장

	int parentIdx = 1;  //루트 노드가 위치해야할 인덱스 값 저장
	int childIdx;

	while (childIdx = GetHipriChildIDX(ph, parentIdx))
	{
		//if (lastElem.pr <= ph->heapArr[childIdx].pr)        
		//	break;                                          

		if (ph->Comp(lastElem , ph->heapArr[childIdx]) >=0)
			break;


		ph->heapArr[parentIdx] = ph->heapArr[childIdx];
		parentIdx = childIdx;                               //마지막 노드가 저장될 위치정보를 한 레벨 내림
	}
	//반복문 탈출하면 parentIdx에는 마지막 노드의 위치정보가 저장됨
	ph->heapArr[parentIdx] = lastElem;           //마지막 노드 최종 저장
	ph->numOfData -= 1;                          //총 데이터 수 -1
	return retData;
}

comp에 등록된 함수의 호출결과를  통해서 우선순위를 판단한다

 

▣ 힙 구현 :  main의 변경 

int main()
{
	Heap heap;
	HeapInit(&heap , DataPriorrity);

	HInsert(&heap, 'A');
	HInsert(&heap, 'B');
	HInsert(&heap, 'C');
	cout << HDelete(&heap) << "\n";

	HInsert(&heap, 'A');
	HInsert(&heap, 'B');
	HInsert(&heap, 'C');
	cout << HDelete(&heap) << "\n";

	while (!HIsEmpty(&heap))
	{
		cout << HDelete(&heap) << "\n";
	}

	return 0;
}