글 읽기 - 힙소트 질문입니다

peterjdw 2년 전 0

이게 왜 틀렸는지 모르겠어요 ㅠㅠ 예시로 했을때는 잘되는데,,

힙소트 이용했습니다

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int size = 0;
int arr[1000005] = { 0 };

void insert(int value) {
	size++;
	arr[size] = value;
	int tmp = size;
	while (arr[tmp / 2] > arr[tmp] && tmp>1) {
		int swap = arr[tmp / 2];
		arr[tmp / 2] = arr[tmp];
		arr[tmp] = swap;
		tmp /= 2;
	}
}

int ExtractMin() {
	int tmp = arr[1];
	arr[1] = arr[size];
	int ind = 1;
	size--;
	int bl = 0;
	if (ind*2<=size&&(arr[ind] > arr[ind * 2 + 1] || arr[ind]>arr[ind*2]) ) {
		bl = 1;
    }
	else {
		bl = 0;
	}

	while (bl==1) {
        if(ind*2>100000) break;
		if (arr[ind * 2 + 1] > arr[ind * 2] && ind*2<=size) {
			int swa = arr[ind];
			arr[ind] = arr[ind * 2];
			arr[ind * 2] = swa;
			ind = ind * 2;
		}
		else if(arr[ind*2]>arr[ind*2+1] && ind*2+1<=size){
			int swa = arr[ind];
			arr[ind] = arr[ind * 2 + 1];
			arr[ind * 2 + 1] = swa;
			ind = ind * 2 + 1;
		}
		if ((arr[ind] > arr[ind * 2 + 1] || arr[ind]>arr[ind*2]) && ind*2<=size){
            bl = 1;
        }
		else {
			bl = 0;
		}
	}
	return tmp;
}

int main(void) {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int a;
		scanf("%d", &a);
		insert(a);
	}
	while(size>=1) {
		int mmm;
		mmm = ExtractMin();
		printf("%d ", mmm);
	}

}

lcr7324 2년 전 1

33번 줄을 다시 보세요.

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

문제

문제

출처

ICPC

힙소트 질문입니다

peterjdw 2년 전 0

lcr7324 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말