글 읽기 - 우선순위 큐 구현 질문입니다.

unta 1년 전 0

C언어에서 힙을 직접 구현해 풀이해봤는데 오답 처리되어 질문 남겨봅니다.

첨부한 코드에 어떤 오류가 있을까요?

동일한 코드로 다른 힙을 이용하는 문제를 통과했어서 질문 드립니다.

#include <stdio.h>

#define HEAP_SIZE 100000

int h[HEAP_SIZE];
int h_count;

int get_parent(int i)
{
    return (i - 1) / 2;
}

int get_child(int i)
{
    return 2 * i + 1;
}

void reheap_down(int node)
{
    int child = get_child(node);

    while (child < h_count)
    {
        int left = h[child];
        int right = child + 1 < h_count ? h[child + 1] : 0;

        int max;
        if (child + 1 < h_count)
            max = left > right ? child : child + 1;
        else
            max = left;

        if (h[node] >= h[max])
            break;
        
        int temp = h[node];
        h[node] = h[max];
        h[max] = temp;

        node = max;
        child = get_child(node);
    }
}

void heapify()
{
    int n = h_count;
    if (n % 2 == 0)
        n--;

    while (n > 0)
    {
        int parent = get_parent(n);
        reheap_down(parent);
        n -= 2;
    }
}

void push(int i)
{
    h[h_count++] = i;

    int node = h_count - 1;
    int parnet = get_parent(node);
    while (parnet >= 0)
    {
        if (h[parnet] >= h[node])
            break;
        
        int temp = h[parnet];
        h[parnet] = h[node];
        h[node] = temp;

        node = parnet;
        parnet = get_parent(node);
    }
}

int pop()
{
    if (h_count == 0)
        return 0;

    int ret = h[0];
    h[0] = h[--h_count];
    h[h_count + 1] = 0;

    reheap_down(0);

    return ret;
}

int N;

int main(void)
{
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        int temp;
        scanf("%d", &temp);

        if (temp != 0)
            push(temp);
        else
            printf("%d\n", pop());
    }

    return 0;
}

unta 1년 전 1

힙 구현을 보완하다 잘못 작성한 부분이 있었습니다.

아래의 코드에서 인덱스 대신에 실제 값을 대입하는 것으로 잘못 구현함을 볼 수 있습니다.

int max;
    if (child + 1 < h_count)
    max = left > right ? child : child + 1;
else
    max = left;

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

문제

문제

출처

ICPC

우선순위 큐 구현 질문입니다.

unta 1년 전 0

unta 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말