[자료구조] Tree(트리) - 우선순위 큐와 힙

 

1. 우선순위 큐를 구현하는 방법

• 배열 기반
• 연결 리스트 기반
• 힙 기반

 

	배열 기반	연결 리스트 기반
단점	삽입/삭제 시 모든 데이터를 한칸씩 이동, 우선순위 비교 시 모든 데이터와 비교	삽입 위치를 찾기 위해 처음부터 마지막까지 데이터의 우선순위 비교

 

이런 이유로 힙으로 구현하는 것이 가장 쉽다.

 

2. 힙

 

힙이란 ? 

: 완전 이진 트리의 일종으로 루트 노드에 우선 순위가 가장 높은 데이터를 위치시킬 수 있는 자료구조

 

힙의 종류

• Max Heap : 모든 노드에 저장된 값은 자식 노드의 값보다 크거나 같아야 함.
• Min Heap : 모든 노드에 저장된 값은 자식 노드의 값보다 작거나 같아야 함.

 

3. 우선순위 큐의 구현

 

 1) 데이터 저장

 

과정을 간략하게 보면,

 

• 새 데이터를 마지막 위치에 저장
• 계속해서 부모 노드와 비교
  
  • 부모 노드보다 우선순위가 높으면 서로 위치 바꿈
  • 부모 노드보다 우선순위가 낮으면 그대로

   이 과정을 부모 노드보다 우선 순위가 낮을 때까지 반복한다.

 

 

1. 3을 마지막 위치에 저장하고 부모 노드인 8과 비교한다.

    2. 3이 8보다 우선순위가 높으므로 교환, 부모노드인 4와 비교

 

 

 

    3. 3이 4보다 우선순위가 높으므로 교환, 부모노드인 1과 비교

 

 

   4. 3보다 1이 우선순위가 높으므로 교환하지 않는다.

 

 

 

데이터 저장 과정에서 트리의 높이가 하나 늘어날 때마다 비교 연산의 횟수가 하나 증가하므로

시간복잡도는 O(logn)으로 계산할 수 있다.

 

 

---

 

 2) 데이터 삭제

 

우선순위 큐에서의 삭제는 우선순위가 높은 데이터의 삭제를 뜻하므로, 루트 노드의 삭제를 구현할 것이다.

 

과정을 간략하게 보면,

• 가장 마지막 노드를 루트 노드의 자리로 옮긴다.
• 자식 노드와 비교(우선 순위가 높은 자식 노드와 비교함.)
  • 자식 노드보다 우선순위가 낮은 경우 서로 위치 바꿈

이 과정을 더 이상 우선 순위가 높은 자식 노드가 없을 때까지 반복한다.

 

 

 

   1. 루트 노드가 삭제된 상태

 

 

 

   2. 마지막 노드를 루트 노드에 위치

 

   3. 우선 순위가 높은 3과 비교

 

 

   4. 3이 8보다 우선순위가 높으므로 교체, 우선 순위가 높은 자식노드인 4와 비교

 

 

 

   5. 4가 8보다 우선순위가 높으므로 교체, 8의 자식 노드는 우선순위가 낮으므로 X

 

   6. 루트 노드 삭제 완료

 

 

데이터 삭제 또한 트리 높이가 하나 늘어날 때마다 비교 연산의 횟수가 하나 증가하므로 

시간복잡도는 O(logn)이다.

 

 

---

 

 

 

4. 힙의 구현

 

우선순위 큐를 구현하는 가장 효율적인 방법은 힙이다. 힙도 '트리'의 일종이므로 힙을 구현하는 방법도 선택해야 한다.

배열과 연결리스트 기반 중 선택할 수 있는데, 연결리스트는 새 노드를 힙의 마지막 위치에 추가하기가 쉽지 않다. 따라서 배열로 구현하고자 한다.

 

 

 

 

1. int GetHiPriChildIdx(Heap * ph, int idx) : 우선 순위를 비교해 우선 순위가 높은 자식 노드를 반환하는 함수

 

데이터의 저장이나 삭제에서 반드시 필요한 과정이 자식 노드의 우선순위를 비교하는 것이다.

 

먼저, 자식 노드가 존재하는 지 확인해야 한다.

왼쪽 자식을 비교하는 이유는 왼쪽 자식 노드가 없다면 오른쪽 자식 노드도 존재하지 않기 때문이다.

if (GetLChildIdx(idx) > ph->numOfData)
    	return 0;

 

자식 노드가 존재하는지 확인했다면, 오른쪽과 왼쪽 자식 노드가 모두 존재하는지 확인해야 한다.

비교할 오른쪽 자식 노드가 존재하지 않으므로 왼쪽 노드의 인덱스를 반환한다.

else if (GetLChildIdx(idx) == ph->numOfData)
    	return GetLChildIdx(idx);

 

자식 노드가 마지막 노드도 아니라면, 왼쪽 자식 노드와 오른쪽 자식 노드의 우선순위를 비교한다.

왼쪽 자식 노드의 pr이 더 크다는 것은 오른쪽 자식 노드의 우선순위가 높다는 의미다.

따라서 오른쪽 자식 노드의 인덱스 반환. 반대도 마찬가지.

else {
    	if (ph->heapArr[GetLChildIdx(idx)].pr > ph->heapArr[GetRChildIdx(idx)].pr)
        	return GetRChildIdx(idx);
        else
        	return GetLChildIdx(idx);
}

 

 

자식 노드의 우선순위 비교 함수를 완성하면 다음과 같다.

int GetHiPriChildIdx(Heap * ph, int idx) { // 우선 순위가 높은 자식 노드 반환
	if (GetLChildIdx(idx) > ph->numOfData)
    	return 0;
    	else if (GetLChildIdx(idx) == ph->numOfData)
    		return GetLChildIdx(idx);
    	else {
    		if (ph->heapArr[GetLChildIdx(idx)].pr > ph->heapArr[GetRChildIdx(idx)].pr)
        		return GetRChildIdx(idx);
        	else
        		return GetLChildIdx(idx);
    	}
}

 

 

2. void HInsert(Heap * ph, HData data, Priority pr) : 데이터 저장 함수

 

새 데이터를 가장 마지막 위치에 저장하고 부모노드와 계속해서 비교한다.

void HInsert(Heap * ph, HData data, Priority pr) {
	int idx = ph->numOfData + 1;
    	HeapElem nelem = {pr, data};
    
    	while (idx != 1) {
    		if (pr < (ph->heapArr[GetParentIdx].pr)) {
        		ph->heapArr[idx] = ph->heapArr[GetParentIdx];
            	idx = GetParentIdx;
        	}
        	else 
        		break;
            
        	ph->heapArr[idx] = nelem;
        	ph->numOfData += 1;
    	}
}

 

 

3. HData HDelete(Heap * ph) : 데이터 삭제 함수

 

데이터를 삭제하려면 마지막 노드를 루트 노드로 위치한 다음 자식 노드와 비교해 아래로 내려가는 과정을 반복해야 한다.

실제 구현에서는 그냥 마지막 노드와 루트 노드의 자식 노드를 비교해서 마지막 노드의 우선 순위가 높을 때까지 반복한 후 제자리에 저장하면 된다.

 

루트 노드의 우선 순위가 높은 자식 노드와 비교를 시작하고, 마지막 노드보다 높은 순위의 노드가 없을 때까지 반복한다.

마지막 노드보다 순위가 높다면 교체한다.

 

HData HDelete(Heap * ph) {
	HData retData = (ph->heapArr[1]).data; // 루트 노드의 데이터를 임시 저장 
    	heapElem lastElem = ph->heapArr[ph->numOfData]; // 마지막 노드 저장
    
    	int parentIdx = 1; // 마지막 노드가 저장될 index
    	int childIdx;
    
    	while (childIdx = GetHiPriChildIdx(ph, parentIdx)) { // 우선순위가 높은 자식노드와 비교
    		if (lastElem.pr <= ph->heapArr[childIdx].pr)
        		break;
        	ph->heapArr[parentIdx] = ph->heapArr[childIdx];
        	parentIdx = childIdx;
   	}
    
    	ph->heapArr[parentIdx] = lastElem;
    	ph->numOfData -= 1;
    	return retData;
}

 

 

 

---

 

// SimpleHeap.h


#ifdef __SIMPLE_HEAP_H__
#define __SIMPLE_HEAP_H__

#define TRUE 1
#define FALSE 0

#define HEAP_LEN 100

typedef char HData;
typedef int Priority;

typedef struct _heapElem {
	Priority pr;
    HData data;
} HeapElem;

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

void HeapInit(Heap * ph);
int HIsEmpty(Heap * ph);

void HInsert(Heap * ph, HData data, Priority pr);
HData HDelete(Heap * ph);

#endif

 

 

// SimpleHeap.c

#include "SimpleHeap.h"

void HeapInit(Heap * ph) { // 힙 초기화
	ph->numOfData = 0;
}

int HIsEmpty(Heap * ph) { // 힙이 비었는지 확인
	if (ph->numOfData == 0)
    	return 1;
    else
    	return 0;
}

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

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

int GetRChildIdx(int idx) {
	return (idx * 2) + 1;
    // return GetLChildIdx(idx) + 1
}

int GetHiPriChildIdx(Heap * ph, int idx) { // 우선 순위가 높은 자식 노드 반환
	if (GetLChildIdx(idx) > ph->numOfData)
    	return 0;
    else if (GetLChildIdx(idx) == ph->numOfData)
    	return GetLChildIdx(idx);
    else {
    	if (ph->heapArr[GetLChildIdx(idx)].pr > ph->heapArr[GetRChildIdx(idx)].pr)
        	return GetRChildIdx(idx);
        else
        	return GetLChildIdx(idx);
    }
}
    	

void HInsert(Heap * ph, HData data, Priority pr) {
	int idx = ph->numOfData + 1;
    HeapElem nelem = {pr, data};
    
    while (idx != 1) {
    	if (pr < (ph->heapArr[GetParentIdx].pr)) {
        	ph->heapArr[idx] = ph->heapArr[GetParentIdx];
            idx = GetParentIdx;
        }
        else 
        	break;
            
        ph->heapArr[idx] = nelem;
        ph->numOfData += 1;
    }
}
	
HData HDelete(Heap * ph) {
	HData retData = (ph->heapArr[1]).data;
    heapElem lastElem = ph->heapArr[ph->numOfData];
    
    int parentIdx = ;
    int childIdx;
    
    while (childIdx = GetHiPriChildIdx(ph, parentIdx)) {
    	if (lastElem.pr <= ph->heapArr[childIdx].pr)
        	break;
        ph->heapArr[parentIdx] = ph->heapArr[childIdx];
        parentIdx = childIdx;
   	}
    
    ph->heapArr[parentIdx] = lastElem;
    ph->numOfData -= 1;
    return retData;
}

 

 

 

** 우선순위 큐 vs 힙

• 우선순위 큐 : ADT 
• 힙 : Data Structure

=> 힙은 우선순위 큐를 구현하는 구현체이며 힙과 우선순위 큐가 동일하지 않다.

---

참고

https://guides.codepath.com/compsci/Heaps