안녕지구 #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