[예제] 힙 정렬 구현

Heap Sort

▶ Heap 구조가 궁금한 경우  [그래프] 힙(Heap) 

힙(Heap) 자료구조란?

▶ Heap Sort 원리 및 시뮬레이션  힙 정렬 (Heap Sort) 

힙 정렬 (Heap Sort)

 

 Input 

2

10

10 49 38 17 56 92 8 1 13 55

13

4 22 50 13 5 1 22 35 21 7 99 100 14

 

 Output 

#1 1 8 10 13 17 38 49 55 56 92

#2 1 4 5 7 13 14 21 22 22 35 50 99 100

#include <stdio.h>
#define MAX_SIZE 100
struct Heap {
    int heap[MAX_SIZE];
    int heapSize = 0;
    void init(void) {
        heapSize = 0;
    }

    int push(int value) {
        if (heapSize + 1 > MAX_SIZE) {
            printf("queue is full!");
            return 0;
        }
        heap[heapSize] = value;
        int current = heapSize;
        while (current > 0 && 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 pop(int *value) {
        if (heapSize <= 0) return -1;
        *value = 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;
            if (heap[current] < heap[child])
                break;
            int temp = heap[current];
            heap[current] = heap[child];
            heap[child] = temp;
            current = child;
        }
        return 1;
    }
}pq;

int main(int argc, char* argv[]){
    int T, N;
    freopen("input.txt", "r", stdin);
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++){
        scanf("%d", &N);
        pq.init();
        for (int i = 0; i < N; i++){
            int value;
            scanf("%d", &value);
            pq.push(value);
        }
        printf("#%d ", test_case);
        for (int i = 0; i < N; i++){
            int value;
            pq.pop(&value);
            printf("%d ", value);
        }
        printf("\n");
    }
}

 

구조체 정렬

구조체 변수를 통해서 여러 기준으로 정렬

▶ [ps] 문자열 사전 오름차순 비교 및 정렬  

[ps] 문자열 사전 오름차순 비교 및 정렬

▶ [ps] 여러 정수 기준에 따른 우선순위 비교 및 정렬  

[ps] 여러 정수 기준에 따른 우선순위 비교 및 정렬

 Input 

3

20 20

20 30

30 10

 

 Output 

30 10

20 30

20 20

#include <stdio.h>
#define MAX_SIZE 100

struct Node {
    int age, exp;
};

int comp(Node A, Node B) {
    if (A.age > B.age) return 1;
    else if (A.age == B.age)
        return A.exp - B.exp;
    return false;
}

inline void swap(Node &A, Node &B) { Node temp = A; A = B; B = temp; }

struct Heap {
    Node heap[MAX_SIZE];
    int heapSize = 0;
    void init(void) {
        heapSize = 0;
    }
    int push(Node value) {
        if (heapSize + 1 > MAX_SIZE) {
            printf("queue is full!");
            return 0;
        }
        heap[heapSize] = value;
        int current = heapSize;
        while (current > 0 && comp(heap[current], heap[(current - 1) / 2])){
            Node temp = heap[(current - 1) / 2];
            heap[(current - 1) / 2] = heap[current];
            heap[current] = temp;
            current = (current - 1) / 2;
        }
        heapSize = heapSize + 1;
        return 1;
    }
    int pop(Node *value) {
        if (heapSize <= 0) return -1;
        *value = 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 = comp(heap[current * 2 + 1], heap[current * 2 + 2]) ? current * 2 + 1 : current * 2 + 2;
            }
            if (comp(heap[current], heap[child]))
                break;
            Node temp = heap[current];
            heap[current] = heap[child];
            heap[child] = temp;
            current = child;
        }
        return 1;
    }
}pq;

int main(int argc, char* argv[]) {
    int T, N;
    pq.init();
    freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        Node val;
        scanf("%d %d", &val.age, &val.exp);
        pq.push(val);
    }
    for (int i = 0; i < N; i++) {
        Node value;
        pq.pop(&value);
        printf("(%d %d)", value.age, value.exp);
        printf("\n");
    }
}