[백준] 2751 수 정렬하기 2

수 정렬하기2 문제는 사실 STL 정렬로 쉽게 풀 수 있다

이번에는 삼성 B형 준비할 겸 직접 힙소트로 구현해서 풀어보았다

혹시 틀렸으면 댓글좀..!!! 부탁합니다

 

총 3개의 함수 swap,insert,sort 함수를 구현했다

swap은 말그대로 a,b의 수를 바꿔주는 함수다

 

insert는 수를 heap에 넣는 함수로 넣고나서 내가 루트가 아니라면

항상 부모와 크기를 비교해본다. 그래서 만약 내가 더 크다면 체인지! 

swap을 못할때까지 죽쭉 올라가보자!!

 

sort는 pop하는걸 n번 연속으로 한다고 생각하면 쉽다

추가적인 배열을 만들필요가 없어서 메모리에 좋다..!

먼저 최대힙이므로 루트에는 가장 큰 수가 있다

이 수를 가장 마지막 last수와 바꾸준다

그럼 가장 뒤에는 가장 큰 수가 위치한다

이제 루트에 올라간 heap[last] 였던 친구의 정확한 위치를 찾기 위해

나의 오른쪽, 왼쪽 자식과 크기를 비교해보자!

이 때 오른쪽,왼쪽 자식이 지금보고있는 크기 last보다 작아야만한다!

=> heap 사이즈보다 작아야한다는 얘기다

만약 자식중에 나보다 큰게있다면 바꿔주고 내려가서 또 반복한다!

이렇게 정렬을 끝내면 오름차순으로 정렬이 완성된다!

 

소스코드

#include <iostream>
using namespace std;
const int N = 1000010;
int heap[N], n,pos=1;
 
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}
 
void insert(int x) {
    int curr = pos++;
    heap[curr] = x;
    while (curr > 1) {
        int parent = curr / 2;
        if (heap[parent] < heap[curr]) {
            swap(heap[parent], heap[curr]);
            curr = parent;
        }
        else break;
    }
}
 
void sort() {
    for (int last = pos - 1; last >= 1; last--) {
        swap(heap[last], heap[1]);
        int curr = 1;
        int r = curr * 2, l = curr * 2 + 1,next;
        while (r < last || l < last) {
            if (r >= last) next = l;
            else if (l >= last) next = r;
            else next = (heap[l] <= heap[r]) ? r : l;
            if (heap[curr] < heap[next]) {
                swap(heap[curr], heap[next]);
                curr = next;
                r = curr * 2;
                l = curr * 2 + 1;
            }
            else break;
        }
    }
}
 
int main() {
    scanf(" %d", &n);
    for (int i = 0; i < n; i++) {
        int x; scanf(" %d", &x);
        insert(x);
    }
    sort();
    for (int i = 1; i <= n; i++) printf("%d\n", heap[i]);
}