힙 정렬 C언어 구현 (백준:11279)

힙 정렬 이란 ?

최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법
내림차순 -- 최대힙
오름차순 -- 최소힙

알고리즘

1. n개의 노드에 대한 완전이진트리를 구성!

• 부모 -> 왼쪽자식 -> 오른쪽 자식 순으로 구성됨

2. 최대힙을 구성한다.

• 부모노드가 자식노드보다 큰 트리
• 아래 부터 루트 까지 순차적으로 올라가며 만들어 갈 수 있다.

3. 가장 큰 수를 가장 작은 수와 교환 한다.
4. 2와 3을 반복한다.

시간 복잡도

O(nlogn)의 복잡도를 가진다. (최악,최선,평균 모두)

백준 11279 번 문제

최대힙 구현 문제

input 값이 0이 들어오면 heappop()
input 값이 x(1 이상의 숫자)가 들어오면 heappush(x)

새로운 노드가 들어온 경우

(이미 힙 정렬이 된 리스트라는 가정)
인덱스 순으로 가장 마지막 위치에 이어서 새로운 요소를 삽입 한다.

만약 리스트에 아무 것도 없다면 삽입만 하고 끝.

앞에 값들이 있는 경우에는
부모와 순차적으로 비교를 해서 교환을 진행한다.

완전 이진 트리를 선형 리스트로 표현 할 경우 현재 노드 idx 의 부모 노드의 인덱스는 idx/2 이다.

부모가 자신보다 커지는 경우 혹은 본인이 root가 되는 경우 까지 반복!

노드를 삭제하는 경우

최대 힙에서 pop 되는 노드는 루트 노드 !
루트 노드를 뺀 후,
루트의 빈 자리에 마지막 index 노드를 가져온다. (마지막 index는 삭제!)
루트에서 부터 왼쪽 자식, 오른쪽 자식 둘중 더 큰 놈과 교환한다.

현재 노드 idx 의 left 는 idx 2 , right 는 idx 2 +1 이다.

리스트의 사이즈를 넘어가기 전까지 반복!

구현 코드

#include<stdio.h>
#define MAX_N 100001

int heap[MAX_N];
int size = 1;

void swap(int a, int b){
    int temp = heap[a];
    heap[a] = heap[b];
    heap[b]= temp;
}

void insert(int data){
    heap[size] = data;
    int now = size;
    size ++;
    if(size == 1) {
        return;
    }
    while(data > heap[now/2] && now != 1){
        swap(now,now/2);
        now = now/2;
    }
}

int delete(){
    if(size == 1)
        return 0;

    int root = heap[1];
    size --;
    heap[1] = heap[size];

    int idx = 1 ; 
    while(idx * 2 < size){
        int left = idx *2 ;
        int right = idx *2 +1;
        int larger = left;
        if (left < size -1 && heap[left] < heap[right]) {
            larger = right;
        }
        if (heap[idx] > heap[larger]){
            break;
        }
        swap(idx,larger);
        idx = larger;
    }
    return root;
}

int main(){
    int n;
    scanf("%d",&n);

    for (int i = 0 ; i < n ; i++) {
        int x; 
        scanf("%d",&x);
        if (x==0){
            printf("%d\n",delete());
        }else{
            insert(x);
        }
    }

    return 0 ;
}