글 읽기 - heap 정렬로 풀어보려는데

pwr2011 6년 전 0

build_max_heap은 잘 되거든요..?

그런데 arr[1]하고 arr[i]바꾸는 부분부터가 잘 안되는거같아요...

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <time.h>
#define lc(x) 2*x
#define rc(x) 2*x+1

using namespace std;
   int n;
void max_heapify(int arr[],int i)
{
    if((arr[lc(i)]==-1)&&(arr[rc(i)]==-1))
        return ;
    else
    {
        int t;
        if(arr[lc(i)]>arr[rc(i)])
            t=lc(i);
        else
            t=rc(i);
            
            if(arr[i]>=arr[t])
                return ;
        int temp=arr[i];
        arr[i]=arr[t];
        arr[t]=temp;
        max_heapify(arr,t);
    }
}
void build_max_heap(int arr[],int heap_size)
{
    for(int i=heap_size/2;i>=1;i--)
        max_heapify(arr,i);

}


void heap_sort(int arr[])
{
    build_max_heap(arr,n);
    for(int i=n;i>=2;)
    {
        int temp=arr[i];
        arr[i]=arr[1];
        arr[1]=temp;
        i--;
        max_heapify(arr,1);
    }
}


int main()
{
    srand(time(NULL));
   int arr[1000001];
   memset(arr,-1,sizeof(arr));
   //cin>>n;
   //for(int i=1;i<=n;i++)
    //   scanf("%d",&arr[i]);
    n=10;
    for(int i=1;i<=n;i++)
        arr[i]=rand()%1000;
    for(int i=1;i<=n;i++)
        printf("%d\n",arr[i]);
    cout<<endl;
    
   heap_sort(arr);
   for(int i=1;i<=n;i++)
    printf("%d\n",arr[i]);
   
   return 0;
}

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

문제

문제

출처

ICPC

heap 정렬로 풀어보려는데

pwr2011 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말