[C언어] 1927번 최소힙 - 힙

#include <stdio.h>

#define SWAP(x, y) do{int tmp; tmp=x; x=y; y=tmp;}while(0)
#define MAX_N 100000

typedef struct _heap {  //힙 구조체
    int arr[MAX_N];
    int size;
} heap;

heap h;

void insert(heap* hp, int data)  //힙 넣기
{
    int here = ++hp->size;
    
    while((here!=1) && (data<hp->arr[here/2])) {
        hp->arr[here] = hp->arr[here/2];
        here/=2;
    }
    hp->arr[here] = data;
}

int deleteData(heap *hp)  //힙 꺼내기
{
    if(!hp->size)
        return 0;
    int ret = hp->arr[1];
    hp->arr[1] = hp->arr[hp->size--];
    int parent = 1;
    int child;
    
    while(child<=hp->size) {
        child =parent*2;
        if(child < hp->size && hp->arr[child]>hp->arr[child+1])
            child++;
        if(hp->arr[hp->size] <= hp->arr[child]) break;
        
        SWAP(hp->arr[parent], hp->arr[child]);
        parent = child;
    }
    return ret;
}

int main()
{
    int N, x;
    int i;
    
    scanf("%d", &N);
    
    for(i=0; i<N; i++) {
        scanf("%d", &x);
        
        if(!x) //0이면 힙에서 숫자 꺼내기
            printf("%d\n", deleteData(&h));
        else  //아니면 힙에 숫자 추가하기
            insert(&h, x);
    }

    return 0;
}

 

힙이라는 자료구조를 쓰라고 해서 힙을 공부했다.

28ms가 나왔고 똑같이 힙을 쓴 다른 사람 코드를 봤었는데 솔직히 코드의 차이점을 잘 모르겠다....

참고한 사이트는 아래에 있다.

 

 

<자료구조 힙 구현>

https://reakwon.tistory.com/42

[자료구조] 그림으로 쉽게 보는 힙(Heap) 개념과 코드

 

<똑같은데 시간 차이가 나는 코드(풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/14903489

로그인

 

<구조체 초기화 하는 법>

https://dojang.io/mod/page/view.php?id=438 

C 언어 코딩 도장: 52.1 구조체와 메모리를 간단하게 0으로 설정하기

 

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.