Maximum Priority Queue

Maximum Priority Queue

• Heap data sturcture 사용한다.

✏️ Heap Data Structure의 특징
1. n개의 입력이 있을 때 트리의 높이는 log(n)이다.
2. n개의 입력이 있을 때 마지막 level에 있는 leaf 노드들의 개수는 최대 n/2이다.

Insert 함수

: 마지막 leaf에 node 추가한다
: 부모와 크기를 비교하며 적절한 위치에 갈 때까지 부모와 자리를 바꾼다.

void insert(int** data, int size, int num) {
	int* temp = (int*)malloc(sizeof(int) * size + 1);
	
	for (int i = 0; i < size + 1; i++) {
		temp[i] = (*data)[i];
	}

	(*data) = (int*)realloc((*data), sizeof(int) * size + 1);

	for (int i = 0; i < size; i++) {
		(*data)[i] = temp[i];
	}
	(*data)[size] = num;

	while ((*data)[size] > (*data)[(size - 1) / 2]) {
		swap(&(*data)[size], &(*data)[(size - 1) / 2]);
		size = (size - 1) / 2;
	}
}

• 메모리 크기 추가를 위해야 realloc을 사용하였다.

• realloc 과정에서 발생할 수 있는 데이터 손실을 방지하기 위해 temp로 data를 덧씌웠다.

Extract 함수

: root 노드에 있는 값을 복사한다.
: 마지막 left 노드의 값을 root노드에 넣고 heap의 크기를 1 줄인다.
: root 노드를 heapify한다.

int extract_max(int** data, int size) {
	int k = (*data)[0];

	swap(&(*data)[0], &(*data)[size - 1]);

	(*data) = (int*)realloc((*data), sizeof(int) * size - 1);

	maxHeapify((*data), 0, size - 1);

	return k;
}

• 마찬가지로 realloc을 이용해 메모리 크기를 하나 줄인다.