글 읽기 - [c] 배열을 통한 최소힙

mun9769 2년 전 0

어디가 틀렸을까요?

찾아주시면 감사합니다

#include <cstdio>
#include <cstdlib>
#define Swap(type, x, y) do { type t = x; x=y; y=t; } while(0)

int a[100002];

void Delete(int *a, int n)
{
    a[0] = a[n];
    a[n] = 0;
    int i=0;
    while(1)
    {
        int min = a[2*i+1] < a[2*i+2] ? 2*i+1 : 2*i+2;
        if(min >= n) break;

        if(a[i] <= a[min]) break;
        else
        {
            Swap(int, a[i], a[min]);
            i = min;
        }
    }
}

void Add(int *a, int data, int n)
{
    a[n] = data;
    while(n > 0) {
        if(a[n] < a[(n-1)/2])
            Swap(int,a[n],a[(n-1)/2]);
        else break;
        n = (n-1) / 2;
    }
}

int main()
{
    int N, i=0;
    scanf("%d", &N);
    int idx = 0;

    int x;
    while(scanf("%d", &x) != EOF)
    {
        if(x == 0){
            printf("%d\n", a[0]);
            if(idx <= 0) continue;
            Delete(a, --idx);
        }
        else {
            Add(a, x, idx++);
        }
    }
    return 0;
}

mun9769 2년 전 0

1. 자식이 하나인 경우 에러가 발생함

2. 14번 줄의 min값이 올바르지 않다.

반례) 8 8 9 0 0 0

출력) 8 9 8

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[c] 배열을 통한 최소힙

mun9769 2년 전 0

mun9769 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말