[백준] 11279번 최대 힙 문제 풀이/히프(Heap)(2)

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

히프 자료구조에 대한 설명글은 다음과 같습니다.

>>이전 글 : https://nomadsjh.tistory.com/41

비선형 자료구조 - 히프(Heap)와 삽입 및 삭제 연산

이 글에서는 최대 히프 문제풀이를 통해 히프에서의 삽입, 삭제 연산을 코드로 구현하는 방법을 다룹니다.

 

문제

 

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

아이디어

 

(우선순위 큐 코드에 대한 설명은 하지 않고 히프 자료 구조를 이용한 코드에 대해서만 아이디어를 설명하겠습니다.)

문제 조건에 의해 입력받는 변수가 0이라면 히프에서의 삭제 연산, 0이 아니라면 삽입 연산을 진행할 것입니다.

따라서 이에 따른 함수들이 필요할 것입니다.

먼저 삽입 연산부터 살펴보겠습니다.

 

• 삽입

히프 자료구조에서 새로운 노드가 삽입될 위치는 가장 마지막 노드입니다.

이 위치를 기억할 변수인 idx를 활용하여 inp[++idx] = x를 해줍니다.

방금 한 과정이 히프의 마지막 노드 위치에 새로운 x값을 대입한 과정입니다.

이때, 이 새로 생긴 히프 구조가 최대 히프 구조를 만족하도록 해주는 함수(up)를 호출합니다.

이 up함수에서의 종료조건은 k==1일 때, 즉 루트 노드에 도달했을 때입니다.

그 전까지는 맨 마지막 노드에서 루트 노드까지 자식 노드값과 부모 노드값을 비교하며

최대 히프 구조를 만족하도록 조건문에 따라 swap을 하고 up(k/2)를 재귀적으로 호출합니다.

 

• 삭제

만약 배열이 비어있다면 0을 출력합니다.

그렇지 않다면 루트 노드(inp[1])을 출력하고 마지막 노드( inp[idx] )를 루트 노드에 대입합니다.

그리고 마지막 노드에 0을 대입합니다.

down(1) 함수를 실행해 루트 노드부터 내려가면서 최대 히프 구조를 만족하도록 해줍니다.

이 down함수에서의 종료 조건은 자식 노드가 없을 때입니다.

두 개의 자식 노드 중 더 큰 값을 c로 설정하고 만약 부모 노드값보다 c값이 더 크다면

swap하고 down(c)를 재귀적으로 호출합니다.

 

소스코드

 

1. 히프 구조를 이용한 풀이

#include <iostream>
using namespace std;
int N;
int tmp, idx; // idx=마지막 값이 저장된 위치
int inp[1<<20];

void up(int k)
{
    if(k==1)return;
    if(inp[k/2]<inp[k]) //if(부모노드<자식노드)
    {
        swap(inp[k/2],inp[k]);
        up(k/2);
    } //swap
}

void push(int x)
{
    inp[++idx]=x;
    up(idx);
} // 힙에 새로운 값 삽입

void down(int k)
{
    int c;
    // 자식 노드가 없으면
    if(!inp[k*2]&&!inp[k*2+1]) return;
    else
    {
        if(inp[k*2]<inp[k*2+1])c=k*2+1;
        else c=k*2;
        // 자식 노드 값 비교하여 c 설정
        if(inp[c]>inp[k])
        {
            swap(inp[c],inp[k]);
            down(c);
        }
    }
}

void pop() //힙의 삭제 연산
{
    if(idx==0) printf("0\n"); // 예외
    else
    {
        printf("%d\n",inp[1]);
        inp[1]=inp[idx]; // 마지막(idx) 노드를 루트(inp[i])에 대입
        inp[idx--]=0; // 마지막 노드에 0 대입
        down(1); // 루트 노드부터 내려가며 inp[idx]의 자리를 찾기
    }
}

int main()
{
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        scanf("%d",&tmp);
        if(tmp!=0) push(tmp);
        else pop();
    }
    return 0;
}

 

2. 우선순위 큐를 이용한 풀이

#include <iostream>
#include <queue>
using namespace std;
priority_queue<int>pq;
int N,tmp;
int main()
{
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        scanf("%d",&tmp);
        if(tmp!=0) pq.push(tmp);
        else
        {
            if(pq.empty())printf("0\n");
            else
            {
                printf("%d\n",pq.top());
                pq.pop();
            }
        }
    }
    return 0;
}