글 읽기 - 힙정렬 런타임 오류... visual stdio에서는 잘돌아가는데ㅜㅠ

kwl3434 6년 전 0

visual stdio 2017에서는 잘돌아가는데 여기서 제출하면 런타임 오류만 뜨네요ㅠㅠ

디버깅도 해봤는데 어디가 잘못된건지 감도 안잡혀요ㅜㅜ

지나가던 고수님들 알려주시면 정말 감사하겠습니다!

#include<stdio.h>
#include<stdlib.h>
#define TRUE	1
#define FALSE	0

/*** Heap의 정의 ****/
#define HEAP_LEN	100

typedef long long int HData;

// d1의 우선순위가 높다면 0보다 큰 값
// d2의 우선순위가 높다면 0보다 작은 값
// d1과 d2의 우선순위가 같다면 0을 반환
typedef long long int PriorityComp(HData d1, HData d2);

typedef struct _heap
{
	PriorityComp * comp;
	int numOfData;
	HData heapArr[HEAP_LEN];
} Heap;



/*** Heap 관련 연산들 ****/
void HeapInit(Heap * ph, PriorityComp pc);
long long int HIsEmpty(Heap * ph);

void HInsert(Heap * ph, HData data);
HData HDelete(Heap * ph);
long long int PriComp(long long int n1, long long int n2)
{
	return n2 - n1;
	//	return n1-n2;
}
void HeapSort(long long int *arr,int n, PriorityComp pc)
{
	Heap heap;
	int i;

	HeapInit(&heap, pc);

	// 정렬 대상을 가지고 힙을 구성한다.
	for (i = 0; i<n; i++)
		HInsert(&heap, *(arr + i));

	// 순서대로 하나씩 꺼내서 정렬을 완성한다.
	for (i = 0; i<n; i++)
		*(arr + i) = HDelete(&heap);
}
int main() {
	int N = 0, K = 0;
	long long int temp=0;
	scanf("%d %d", &N, &K);
	long long int* A = (long long int*)malloc(sizeof(long long int)*N);
	
	for (int i = 0; i < N; i++) {
		scanf("%lld", (A+i));
	}
	HeapSort(A,N, PriComp);
	printf("%lld\n", *(A+K-1));
	free(A);
}
void HeapInit(Heap * ph, PriorityComp pc)
{
	ph->numOfData = 0;
	ph->comp = *pc;
}

long long int HIsEmpty(Heap * ph)
{
	if (ph->numOfData == 0)
		return TRUE;
	else
		return FALSE;
}

int GetParentIDX(int idx)
{
	return idx / 2;
}

int GetLChildIDX(int idx)
{
	return idx * 2;
}

int GetRChildIDX(int idx)
{
	return GetLChildIDX(idx) + 1;
}

int GetHiPriChildIDX(Heap * ph, int idx)
{
	if (GetLChildIDX(idx) > ph->numOfData)
		return 0;

	else if (GetLChildIDX(idx) == ph->numOfData)
		return GetLChildIDX(idx);

	else
	{
		//	if(ph->heapArr[GetLChildIDX(idx)].pr 
		//				> ph->heapArr[GetRChildIDX(idx)].pr)
		if (ph->comp(ph->heapArr[GetLChildIDX(idx)],
			ph->heapArr[GetRChildIDX(idx)]) < 0)
			return GetRChildIDX(idx);
		else
			return GetLChildIDX(idx);
	}
}

void HInsert(Heap * ph, HData data)
{
	int idx = ph->numOfData + 1;

	while (idx != 1)
	{
		//	if(pr < (ph->heapArr[GetParentIDX(idx)].pr))
		if (ph->comp(data, ph->heapArr[GetParentIDX(idx)]) > 0)
		{
			ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
			idx = GetParentIDX(idx);
		}
		else
		{
			break;
		}
	}

	ph->heapArr[idx] = data;
	ph->numOfData += 1;
}

HData HDelete(Heap * ph)
{
	HData retData = ph->heapArr[1];
	HData lastElem = ph->heapArr[ph->numOfData];

	int parentIdx = 1;
	int childIdx;

	while (childIdx = GetHiPriChildIDX(ph, parentIdx))
	{
		//	if(lastElem.pr <= ph->heapArr[childIdx].pr)
		if (ph->comp(lastElem, ph->heapArr[childIdx]) >= 0)
			break;

		ph->heapArr[parentIdx] = ph->heapArr[childIdx];
		parentIdx = childIdx;
	}

	ph->heapArr[parentIdx] = lastElem;
	ph->numOfData -= 1;
	return retData;
}

seico75 6년 전 1

힙크기가 100이면 너무 작네요

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

문제

문제

출처

ICPC

힙정렬 런타임 오류... visual stdio에서는 잘돌아가는데ㅜㅠ

kwl3434 6년 전 0

seico75 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말