Priority Queue(우선 순위 큐), Heap(Max Heap, Min Heap)

Priority Queue(우선 순위 큐)

• ADT(추상 자료형)
• 데이터 입력 순서에 상관 없이 우선 순위 순으로 처리된다.
• 배열 기반 Heap 을 통해 구현
• scheduler, 네트워크 트래픽 제어 등에 쓰임

※ADT(Abstract Data Type)

어떤 자료형이 가지는 기능과 속성만 명시하고 자료형의 구체적인 구현 방법은 명시하지 않은것

 

Heap(Max Heap, Min Heap)

• 최대값또는 최소값을 빠르게 찾기 위해 쓰인다
• Complete Binary Tree(완전 이진 트리) 이다
• 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있다.
• 마지막 레벨에 노드가 있을 때는 항상 왼쪽부터 순서대로 채워야 한다.
• 배열로 구현한다
• Max Heap 은 항상 부모 노드의 값이 자식노드의 값보다 크다 그래서 root 노드의 값은 최대값이 온다. 최대 값을 빠르게 구할 수 있다.
• Min Heap 은 항상 부모 노드의 값이 자식노드의 값보다 작다, 최소값을 빠르게 구할 수 있다.
• 노드 개수를 알면, 트리구조는 무조건 확정할 수 있다.

 

Heapify algorithm

모든 노드의 위치가 heap 구조를 만족하도록, 위치를 조정하는 알고리즘

어떤 노드가 힙 구조(max-heap 이면 부모노드가 항상크다, min-heap 은 그 반대)를 위반하고 있을때, 그 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘, 위치를 바꾼 뒤에도 여전히 자식이 존재하는 경우, 또 자식 중에서 더 큰 자식과 자신의 위치를 바꾸어야 한다. 자식이 더 이상 존재하지 않을 때 까지 이과정은 계속 반복된다.(min-heap 은 반대로 부모 노드가 항상 자식들 보다 작게 위치를 조정한다)

 

시간 복잡도 :

한 번 자식 노드로 내려갈 때마다 노드의 갯수가 2배씩 증가한다 O(nlogn)

그러나 실제로는 n/2 개수 만큼만 연산을 해줘도 Heapify가 완료 된다 그래서

실제 시간 복잡도는 O(n) 이다

 

 

 

힙 트리 와 배열 인덱스 관계

위 트리 노드의 숫자는 곧 완전 이진트리의 삽입 순서이자, 배열로 힙트리를 표현할때 각각 노드의 인덱스와 동일하다

i번 노드의 부모는 heap[(i / 2)]

i번 노드의 왼쪽 자식은 heap[(2*i)]

i번 노드의 오른쪽 자식은 heap[(2*i) + 1]

 

 

 

 

Insert(삽입)

1.삽입할 데이터를 가장 마지막 자리에 놓기

2.삽입한 데이터의 값을 부모노드와 비교해서 크면 부모노드와 위치를 바꾼다

이것을 부모노드가 더 클때까지 반복한다(heapify algorithm)

 

version 1

void Insert(Max_Heap* _heap, int _iData)
{
	int* arr = _heap->iDataArr;
	int* iSize = &_heap->iSize;


	int currentIndex = ++(*iSize); //맨마지막 노드 인덱스 가져오기


	/*
	맨 마지막 노드에 데이터를 삽입, 해당 데이터가 부모 보다 크면 부모와 위치를 바꾸고 아니면 그대로 둠 
	*/
	while ((currentIndex != 1) && (_iData > arr[currentIndex / 2])) //root가 아니다 && 삽입 데이터가 현재노드의 부모보다 크다
	{
		arr[currentIndex] = arr[currentIndex / 2]; // 자식 노드자리에 부모 노드 값을 대입, 부모노드가 작으므로 밑으로 내림
		currentIndex /= 2; // 현재 인덱스에 부모 인덱스 대입
	}
	arr[currentIndex] = _iData; //최종 위치에 삽입
}

 

 

version 2

void Insert_2(int* arr2, int key, int input)
{
	arr2[key] = input; // 마지막 노드에 입력값 넣기

	while (key > 1)  //root에 도달할때까지 반복
	{
		if (arr2[key] > arr2[key / 2])  // 부모 노드보다 더 크다면
		{
			Swap_int(&arr2[key], &arr2[key / 2]); // 부모 노드와 자리를 바꿈
			key /= 2; // 부모노드 인덱스로 전환
		}
		else
		{
			break;
		}
	}
}

 

Pop(가장 첫번째 원소 삭제와 동시에 빼오기) 

Pop은 std::priority_queue 기준으로 삭제만 되게 되어있다. https://en.cppreference.com/w/cpp/container/priority_queue/pop

std::priority_queue<t,container,compare>::pop - cppreference.com</t,container,compare>

지금부터 구현하는 Pop함수는 약간 변형해서 반환까지 하게 한것이다.

 

힙트리 특성상 루트 노드의 값을 반환하게 되어있고, Max Heap 에서는 최대값, Min Heap 에서는 최소값을 꺼내게 되어있다.

 

 

1.루트 노드값(최대값, 최소값)을 꺼낸다

2.제일 마지막에 위치한 데이터를 루트로 옮긴다

3.자식 노드중에 가장 큰 값의 자리와 바꾼다

이것을 자식 노드보다 클때까지 반복한다(heapify algorithm)

 

 

 

version 1

int Pop(Max_Heap* _heap)
{
	if (_heap->iSize == 0)
	{
		return 0;
	}

	int ret = _heap->iDataArr[1]; // 꺼내올 데이터(root)
	_heap->iDataArr[1] = _heap->iDataArr[_heap->iSize--]; // root 자리에 맨마지막 위치 데이터 대입
	int parent = 1; //root 부터 시작
	int child = 0;
	
	while (1)
	{
		child = parent * 2; //왼쪽 자식, i번 노드의 왼쪽 자식 == heap[(2*i)]
		if (child + 1 <= _heap->iSize && _heap->iDataArr[child] <= _heap->iDataArr[child + 1]) // 오른쪽 자식 인덱스가 존재한다 && 오른쪽 자식이 왼쪽 자식보다 크거나 같다
		{
			child++; //오른쪽 자식으로 전환
		}

		if (child > _heap->iSize || _heap->iDataArr[child] < _heap->iDataArr[parent]) //자식인덱스가 힙 사이즈보다 크다(범위를 넘어버림) || 부모가 제일 큰 자식 보다 크다 
		{
			break; //중단
		}

		Swap_int(&_heap->iDataArr[parent], &_heap->iDataArr[child]); //부모와 제일 큰 자식 자리를 바꿈
		parent = child; // 자식의 자식들을 비교하기위해, 자식 노드를 부모 노드로 봄
	}
	return ret; // 꺼내올 데이터 리턴
}

 

version 2

int Pop_2(Max_Heap* _heap)
{
	int result = _heap->iDataArr[1]; //꺼내올 데이터
	
	int* arr = _heap->iDataArr; 
	int* iSize = &_heap->iSize;
	
	Swap_int(&arr[1], &arr[*iSize]); //마지막 노드 데이터와 루트 데이터를 바꿈
	(*iSize)--; //전체 노드 갯수 감소

	int parentIdx = 1; 
	int childIdx = parentIdx * 2;

	if (childIdx + 1 <= *iSize) //오른쪽 자식 노드 인덱스가 노드 전체 갯수를 넘지 않는다, 즉 오른쪽 자식이 존재한다
	{
		childIdx = (arr[childIdx] > arr[childIdx + 1]) ? childIdx : childIdx + 1; //왼쪽 자식, 오른쪽 자식, 둘 중에 큰 노드 선별
	}

	while (childIdx <= *iSize && arr[parentIdx] < arr[childIdx]) //자식 인덱스가 범위를 넘지 않는다 && 자식노드가 부모노드 보다 크다
	{
		Swap_int(&arr[parentIdx], &arr[childIdx]); // 자식 노드와 부모노드 위치 바꾸기

		parentIdx = childIdx; //자식 노드를 부모 노드로 봄
		childIdx *= 2; //왼쪽 자식 노드

		if (childIdx + 1 <= *iSize) //오른쪽 자식 노드 인덱스가 노드 전체 갯수를 넘지 않는다, 즉 오른쪽 자식이 존재한다
		{
			childIdx = (arr[childIdx] > arr[childIdx + 1]) ? childIdx : childIdx + 1; //왼쪽 자식, 오른쪽 자식, 둘 중에 큰 노드 선별
		}
	}
	return result;
}

 

 

전체 코드

#include <stdio.h>
#include <stdlib.h>

#define DEFAULT_HEAP_MAXSIZE 7

typedef struct _tagMaxHeap
{
	int* iDataArr;
	int iSize;
} Max_Heap;

void Swap_int(int* _a, int* _b);

void InitHeap(Max_Heap* _heap);
void Insert(Max_Heap* _heap, int _iData);
void Insert_2(int* arr2, int key, int input);
int Pop(Max_Heap* _heap);
int Pop_2(Max_Heap* _heap);

int main()
{
	Max_Heap heap;

	InitHeap(&heap);
	Insert(&heap, 8);
	Insert(&heap, 3);
	Insert(&heap, 15);
	Insert(&heap, 6);
	Insert(&heap, 10);
	Insert(&heap, 2);
	Insert(&heap, 18);
	
	/*	
	Insert_2(heap.iDataArr, ++heap.iSize, 8 );
	Insert_2(heap.iDataArr, ++heap.iSize, 3 );
	Insert_2(heap.iDataArr, ++heap.iSize, 15 );
	Insert_2(heap.iDataArr, ++heap.iSize, 6 );
	Insert_2(heap.iDataArr, ++heap.iSize, 18 );
	Insert_2(heap.iDataArr, ++heap.iSize, 2 );
	Insert_2(heap.iDataArr, ++heap.iSize, 10 );
	*/

	for (int i = 0; i < DEFAULT_HEAP_MAXSIZE; i++)
	{
		printf("%d ", Pop_2(&heap));
	}

	return 0;
}

void InitHeap(Max_Heap* _heap)
{
	_heap->iDataArr = (int*)calloc(DEFAULT_HEAP_MAXSIZE, sizeof(int));
	_heap->iSize = 0;
}


/*
i번 노드의 왼쪽 자식 == heap[(2*i)]
i번 노드의 오른쪽 자식 == heap[(2*i) + 1]
i번 노드의 부모 == heap[(i / 2)]
*/
void Insert(Max_Heap* _heap, int _iData)
{
	int* arr = _heap->iDataArr;
	int* iSize = &_heap->iSize;


	int currentIndex = ++(*iSize); //맨마지막 노드 인덱스 가져오기


	/*
	맨 마지막 노드에 데이터를 삽입, 해당 데이터가 부모 보다 크면 부모와 위치를 바꾸고 아니면 그대로 둠 
	*/
	while ((currentIndex != 1) && (_iData > arr[currentIndex / 2])) //root가 아니다 && 삽입 데이터가 현재노드의 부모보다 크다
	{
		arr[currentIndex] = arr[currentIndex / 2]; // 자식 노드자리에 부모 노드 값을 대입, 부모노드가 작으므로 밑으로 내림
		currentIndex /= 2; // 현재 인덱스에 부모 인덱스 대입
	}
	arr[currentIndex] = _iData; //최종 위치에 삽입
}

void Insert_2(int* arr2, int key, int input)
{
	arr2[key] = input; // 마지막 노드에 입력값 넣기

	while (key > 1)  //root에 도달할때까지 반복
	{
		if (arr2[key] > arr2[key / 2])  // 부모 노드보다 더 크다면
		{
			Swap_int(&arr2[key], &arr2[key / 2]); // 부모 노드와 자리를 바꿈
			key /= 2; // 부모노드 인덱스로 전환
		}
		else
		{
			break;
		}
	}
}



int Pop(Max_Heap* _heap)
{
	if (_heap->iSize == 0)
	{
		return 0;
	}

	int ret = _heap->iDataArr[1]; // 꺼내올 데이터(root)
	_heap->iDataArr[1] = _heap->iDataArr[_heap->iSize--]; // root 자리에 맨마지막 위치 데이터 대입
	int parent = 1; //root 부터 시작
	int child = 0;
	
	while (1)
	{
		child = parent * 2; //왼쪽 자식, i번 노드의 왼쪽 자식 == heap[(2*i)]
		if (child + 1 <= _heap->iSize && _heap->iDataArr[child] <= _heap->iDataArr[child + 1]) // 오른쪽 자식 인덱스가 존재한다 && 오른쪽 자식이 왼쪽 자식보다 크거나 같다
		{
			child++; //오른쪽 자식으로 전환
		}

		if (child > _heap->iSize || _heap->iDataArr[child] < _heap->iDataArr[parent]) //자식인덱스가 힙 사이즈보다 크다(범위를 넘어버림) || 부모가 제일 큰 자식 보다 크다 
		{
			break; //중단
		}

		Swap_int(&_heap->iDataArr[parent], &_heap->iDataArr[child]); //부모와 제일 큰 자식 자리를 바꿈
		parent = child; // 자식의 자식들을 비교하기위해, 자식 노드를 부모 노드로 봄
	}
	return ret; // 꺼내올 데이터 리턴
}

int Pop_2(Max_Heap* _heap)
{
	int result = _heap->iDataArr[1]; //꺼내올 데이터
	
	int* arr = _heap->iDataArr; 
	int* iSize = &_heap->iSize;
	
	Swap_int(&arr[1], &arr[*iSize]); //마지막 노드 데이터와 루트 데이터를 바꿈
	(*iSize)--; //전체 노드 갯수 감소

	int parentIdx = 1; 
	int childIdx = parentIdx * 2;

	if (childIdx + 1 <= *iSize) //오른쪽 자식 노드 인덱스가 노드 전체 갯수를 넘지 않는다, 즉 오른쪽 자식이 존재한다
	{
		childIdx = (arr[childIdx] > arr[childIdx + 1]) ? childIdx : childIdx + 1; //왼쪽 자식, 오른쪽 자식, 둘 중에 큰 노드 선별
	}

	while (childIdx <= *iSize && arr[parentIdx] < arr[childIdx]) //자식 인덱스가 범위를 넘지 않는다 && 자식노드가 부모노드 보다 크다
	{
		Swap_int(&arr[parentIdx], &arr[childIdx]); // 자식 노드와 부모노드 위치 바꾸기

		parentIdx = childIdx; //자식 노드를 부모 노드로 봄
		childIdx *= 2; //왼쪽 자식 노드

		if (childIdx + 1 <= *iSize) //오른쪽 자식 노드 인덱스가 노드 전체 갯수를 넘지 않는다, 즉 오른쪽 자식이 존재한다
		{
			childIdx = (arr[childIdx] > arr[childIdx + 1]) ? childIdx : childIdx + 1; //왼쪽 자식, 오른쪽 자식, 둘 중에 큰 노드 선별
		}
	}
	return result;
}


void Swap_int(int* _a, int* _b)
{
	*_a ^= *_b ^= *_a ^= *_b;
}

 

 

실행결과

삽입한 순서에 상관없이 우선 순위(노드 값이 높을 수록 우선순위가 높다고 할때) 순으로 

데이터를 꺼내오고 있다.