수다닷컴

class Heap
{
public static void main(String[] args)
{

int [] m= {3,5,7,2,4,6,9,10,1,8};
//int [] m = {1,2,3,4,5,6,7,8,9,10};
heapSort(m);
System.out.println();
dispM(m);

}
public static void heapTree(int [] m, int n)
{

int temp;
int max;
int b= 0;

do
{
b=0;
for(int i = n/2 - 1; i=0 ;i--)
{max = m[i] m[2*i+1] ? m[2*i+1] : m[i];
if(2*i+2 n)
max = max m[2*i+2] ? m[2*i+2] : max;

if( max == m[2*i + 1])
{
b++;
temp = m[i];
m[i] = m[2*i + 1];
m[2*i + 1] = temp;
}else if (2*i+2n && max == m[2*i+2])
{
b++;
temp = m[i];
m[i] = m[2*i + 2];
m[2*i + 2] = temp;
}

}
}while(b != 0);}
public static void heapSort(int [] m)
{
int temp;
for(int i=0;im.length-1;i++)
{
heapTree(m, m.length-i);
//가장 큰 수를 뒤로....
temp = m[0];
for(int j=0;jm.length-i-1;j++)
m[j]=m[j+1];
m[m.length-i-1]=temp;

}
}

public static void dispM(int [] m)
{
for(int i=0; im.length;i++)
System.out.printf(%-5d , m[i]);
System.out.println();
}
}

힙정렬이 평균적인 정렬 시간을 갖는다는데 힙트리만드는 과정에서 교환횟수로 재는건지 궁금하네요

신청하기