안녕지구 #developer #bompapa

소소한팁 - 원하는 개수 만큼만 정렬하기 2 (Heap)

20 Feb 2020 | 알고리즘 소소한팁

윤재님 코멘트를 받아서 Heap을 이용하여 원하는 개수 n만큼만 정렬하는 것을 구현해보았습니다. Heap구현을 위해 Priority Queue를 사용합니다. 원하는 최종 결과물이 오름차순이라면 Max Heap을 사용하여 숫자가 가장 큰 값부터 뽑아서 배열의 뒤에서부터 저장하는 방식입니다. Priority Queue는 공개되어 있는 코드를 사용했습니다.

Heap이 모두 차 있을 때, 새로 입력하려는 값이 Heap의 Root 값보다 크거나 같으면 범위안에 들지 않기 때문에 제외하고 반대로 Root 값보다 작으면 Pop 하여 가장 큰 값을 제거하고 Heap에 다시 입력합니다. 최종 결과 배열에 Heap이 빌 때까지 모두 넣어주어야 하므로 배열의 크기는 Heap 크기보다 같거나 커야 합니다. 만약 배열의 크기를 n과 같게 하고 싶다면 Heap 크기를 n으로 잡으면 됩니다.

Priority Queue

#define MAX_SIZE 10

int heap[MAX_SIZE];
int heapSize = 0;

int comp(int a, int b) {
	return a >= b;
}

void heapInit(void) {
	heapSize = 0;
}

int heapPush(int value) {
	if (heapSize + 1 > MAX_SIZE) {
		return 0;
	}

	heap[heapSize] = value;

	int current = heapSize;
	while (current > 0 && comp(heap[current], heap[(current - 1) / 2])) {
		int temp = heap[(current - 1) / 2];
		heap[(current - 1) / 2] = heap[current];
		heap[current] = temp;
		current = (current - 1) / 2;
	}

	heapSize = heapSize + 1;

	return 1;
}

int heapPop() {
	if (heapSize <= 0) {
		return -1;
	}

	int ret = heap[0];
	heapSize = heapSize - 1;
	heap[0] = heap[heapSize];

	int current = 0;
	while (current * 2 + 1 < heapSize) {
		int child;
		if (current * 2 + 2 == heapSize) {
			child = current * 2 + 1;
		} else {
			//child = heap[current * 2 + 1] < heap[current * 2 + 2] ? current * 2 + 1 : current * 2 + 2;
			child = comp(heap[current * 2 + 1], heap[current * 2 + 2]) ? current * 2 + 1 : current * 2 + 2;
		}

		//if (heap[current] < heap[child]) {
		if (comp(heap[current], heap[child])) {
			break;
		}

		int temp = heap[current];
		heap[current] = heap[child];
		heap[child] = temp;

		current = child;
	}
	return ret;
}

n개만 정렬하기

#include <stdio.h>

#define SORT_NUM 5
int sample_arr[SORT_NUM];

void insert(int data) {
	// 모두 차 있는 경우
	if (heapSize + 1 > MAX_SIZE) {
		if (data >= heap[0]) return;
		heapPop();
		heapPush(data);
	} else {
		heapPush(data);
	}
}

int main(int argc, char* argv[]) {
	
	heapInit();

	insert(5);
	insert(3);
	insert(8);
	insert(6);
	insert(2);
	insert(4);
	insert(9);
	insert(7);
	insert(1);
	insert(0);

	for (int i = MAX_SIZE - 1; i >= 0; i--) {
		sample_arr[i] = heapPop();
	}

	for (int i = 0; i < SORT_NUM; i++) {
		printf("%d ", sample_arr[i]);
	}
	return 0;
}

출력

1 2 3 4 5

Related Posts

Comments