[자료구조]-힙

1. 최대 힙 (백준 11279)

힙에 대한 주요 핵심

- 힙은 complete tree이다. ==> perfect에서 leaf의 오늘쪽 몇 개가 없는 트리

- 배열을 사용해서 구현. 루트 인덱스가 1

- push(x)의 경우, 배열의 가장 끝에 값을 넣은 후, 트리의 위쪽 방향으로 가면서, 선조 노드와의 값을 비교해서 바꿔가면서 루트까지 진행.

- pop()의 경우, 배열의 첫번째(루트)에 값을 넣은 후, 트리의 하위 후손방향으로 값을 비교해가면서 진행   

-----------------------------

1. 최대 힙 (백준 11279)

최대힙 자료구조를 만들어서 다음의 명령어에 대해 수행하게 하시오.

  1)배열에 자연수 x를 넣는다.

  2)배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

핵심

최대힙의 push(), pop()을 구현하면 됨

소스

#include <stdio.h>

 

int h[100001],t=0;

int N;

void swap(int i, int j){

    int tmp=h[i];

    h[i]=h[j];

    h[j]=tmp;

}

 

void push(int x){

    h[++t]=x;

    for(int i=t;i>1;i/=2){ //i>=1이 아님에 주의

        if(h[i]>h[i/2]) swap(i,i/2);

        else break;

    }

}

 

int pop(){

    int top=h[1];

    h[1]=h[t];

    h[t--]=0;  

    int i=1;

    while(i*2<=t){  

        if(h[i]>h[i*2] && h[i]>h[i*2+1]) break;

        else if (h[i*2]>h[i*2+1]){

            swap(i,i*2); i=i*2;

        }

        else {

            swap(i,i*2+1); i=i*2+1;

        }

    }  

    return top;

}

 

int main(){

    int x;

    scanf("%d",&N);

    while(N--){    

        scanf("%d",&x);

        if(x==0) {

            if(t==0) printf("0\n");

            else printf("%d\n",pop());

        }

        else push(x);      

    }

    return 0;

}

-끝-