Priority_queue 를 최대 Heap 으로 구현해보기

<value, index> 를 priority_queue에 push 한다고 했을 때, pop을 10번 한 결과가 value 값이 가장 크도록 하면서 동일한 경우에 index 값이 작도록 하는 결과가 10개 저장하도록 하는 것을 구현해보겠습니다.

 

일단 value 값이 가장 크도록 하기 위해 최대 Heap 으로 구현했습니다. (Root의 index는 0으로 설정하였음)

 

최대 Heap 의 Push 하는 함수

int heapSize;
int index[100000], Heap[100000], A[10], B[10];

void heap_Push(int i, int value)
{
	Heap[i] = value;
	index[i] = i;

	// Heap 구현
	int cur = i;

	while (cur != 0 && Heap[cur] > Heap[(cur - 1) / 2]) {
		int temp = Heap[cur];
		Heap[cur] = Heap[(cur - 1) / 2];
		Heap[(cur - 1) / 2] = temp;

		temp = index[cur];
		index[cur] = index[(cur - 1) / 2];
		index[(cur - 1) / 2] = temp;

		cur = (cur - 1) / 2;
	}

	heapSize++;
}

 

최대 Heap의 pop을 10번하여 얻고자 하는 value, index를 result 배열에 추출하는 함수 (0~10 의 pop한 갯수를 반환함)

int heap_Pop10(int result[10])
{
	int ret = heapSize > 10 ? 10 : heapSize;

	int size = heapSize;

	for (int i = 0; i < ret; i++) {
		int value = Heap[0], idx = index[0];
		size -= 1;
		Heap[0] = Heap[size];
		index[0] = index[size];

		int cur = 0;
		while (2 * cur + 1 < size) {
			int child;

			if (2 * cur + 2 == size) child = 2 * cur + 1;
			else {
				child = Heap[2 * cur + 1] > Heap[2 * cur + 2] ? 2 * cur + 1 : 2 * cur + 2;
				if (Heap[2 * cur + 1] > Heap[2 * cur + 2]) child = 2 * cur + 1;
				else if (Heap[2 * cur + 1] < Heap[2 * cur + 2]) child = 2 * cur + 2;
				else {
					if (index[2 * cur + 1] < index[2 * cur + 2]) child = 2 * cur + 1;
					else child = 2 * cur + 2;
				}
			}

			if (Heap[cur] > Heap[child]) break;
			if (Heap[cur] == Heap[child]) {
				if (index[cur] > index[child]) {
					int temp = index[cur];
					index[cur] = index[child];
					index[child] = temp;
				}
				else break;
			}
			else {
				int temp = Heap[cur];
				Heap[cur] = Heap[child];
				Heap[child] = temp;

				temp = index[cur];
				index[cur] = index[child];
				index[child] = temp;
			}

			cur = child;
		}
		A[i] = value;
		B[i] = idx;
	}

	for (int i = 0; i < ret; i++) {
		Heap[i] = A[i];
		index[i] = B[i];
		result[i] = index[i];
	}

	return ret;
}