7장 우선순위 큐와 힙

*우선순위 큐는 새 요소에 우선순위를 부여해서 큐에 삽입하고 가장 높은 우선순위를 갖는 요소부터 빠져나오도록 한다.

*힙이란 힙 순서 속성(Heap Order Property)을 만족하는 완전 이진 트리이다. ->완전 이진 트리란 가장 높은 높이의 원소들을 제외하고 왼,오른 자식들이 모두 채워져 있는 트리를 말한다.

-힙 순서 속성이란, 모든 노드는 부모 노드보다 큰 값을 가진다. (루트는 예외)

*힙의 루트노드는 최소값 노드라는걸 항상 보장한다.

Heap의 삽입 연산의 순서를 알아보자.

1.힙의 최고 깊이의 가장 우측에 새 노드를 우선 삽입한다.(완전이진트리 유지)

2.삽입한 노드가 부모노드보다 작아질 때 까지 부모노드와 계속 교환해나간다.

void HEAP_Inser(Heap *heap , ElementType data){
	int currentPosition = heap->UsedSize;
	int ParrentPosition = HEAP_GetParent(currentPosition);

	if(heao->UsedSize == heap->Capacity){
		heap->Capacity *= 2;
		heap->Nodes = (HeapNode*)realloc (heap->Nodes , sizeof(HeapNdde)*heap->Capacity);
	}
	heap->Nodes[currentPosition].data = data;

	/* 부모노드보다 클 때 까지 반복한다. */
	while( currentPosition > 0 && heap->Nodes[currentPosition].data < heap->Nodes[ParrentPosition].data){
		HEAP_SwapNode(heap, currentPosition , ParrentPosition);
		currentPosition = ParrentPosition;
		ParrentPosition = HEAP_GetParent(currentPosition);
	}
	heap->UsedSize++;
}

Heap의 최소값 삭제 연산의 순서를 알아보자.

1.힙의 최고 높은 높이의 최 우측 노드를 루트노드에 위치한다. 

2.자식 노드 중 더 작은 값의 노드와 교환한다. 

3.옮겨온 노드가 자식이 없거나, 자식보다 작을때까지 2번 과정을 반복한다.

void HEAP_Delete(Heap *heap , HeapNode * root ) {
	int parentPositin = 0;
	int leftPosition = 0;
	int rightPosition = 0;

	memcpy(root ,&heap->nodes[0] , sizeof(HeapNode));
	memset(&heap->nodes[0] , 0 , sizeof(HeapNode));

	heap->UsedSize--;
	HEAP_SwapNode(heap , 0 , heap->UsedSize);

	leftPosition = HEAP_GetLeftChild(0);
	rightPosition = leftPosition + 1;

	wihle(1){
		int selectedChild = 0;
		if(leftPosition >= heap->usedSized)
			break;
		if(rightPosition >= heap->usedSized)
			selectedChild = leftPosition;
		else{
			if(heap->Nodes[leftPosition].data > heap->nodes[rightPosition].data)
				selectedChild = rightPosition;
			else
				selectedChild = leftPosition;
		}
		if(heap->Nodes[selectedChild].Data < heap->Nodes[parentPositin].data) {
			HEAP_SwapNodes(heap , parentPositin , selectedChild);
			parentPositin = selectedChild;
		} else
			break;
		leftPosition = HEAP_GetLeftChild(parentPositin);
		rightPosition = leftPosition +1;
		
	}

}

*여기서 힙의 구현은 배열로 한다.루트부터, 좌측부터 배열에 차곡차곡 쌓는다.

typedef int ElementType;
typdef struct tagHeapNode{
	ElementType Data;
} HeapNode;

typedef struct tagHeap {
	HeapNode* Nodes;
	int Capacity;
	int UsedSize;
} Heap;

*우선순위 큐는 힙와 개념이 똑같다. 단지 '우선순위'라는 데이터만 추가해줘서 삽입될 때 해당하는 우선순위의 위치에 삽입이 되며, 가장 급한(가장 우선순위가 높은) 원소가 우선 삭제된다.