Heap sort 알고리즘을 이용하여 정수배열을 순서대로 정렬시키는 함수를 만든 예제입니다.


/////////////////////////////////////////////////
// 
//   Author: Jisang Yoo
//
//   H@_@p sort
//
/////////////////////////////////////////////////

/*Sort the array 'data[]'*/
void SortIntArray(int a[],int n);

/*Fix the Heap 'heap[]' (In other words, down_heap the heap 'heap[]').
'hn'is the size of the heap.('hn'is the size of 'heap[]' as a heap not as an array.
heap[1]is the first element of the heap. and heap[n]is the last element.
Imagin the array of BASIC.)
't'is the node to fix(or to down_heap).
This function does not change the value of heap[0].(It is for convenience)*/
void FixIntHeap(int heap[], int hn,int t);

void FixIntHeap(int heap[], int hn,int t)
{
  int i,temp=heap[t];
  while(i=2*t,i<=hn)/*while 't'is an internal node*/
  {
    if(i+1<=hn && heap[i]<heap[i+1])/*if 't' have two son and her right son is the bigger.*/
      i=i+1;
    if(heap[i]>temp)/*if the son is bigger than the mother 't'*/
    {
      heap[t]=heap[i];
      t=i;
    }
    else
      break;
  }
  heap[t]=temp;
}

void SortIntArray(int a[],int n)
{
  int i,temp;

  /*Construct heap of size n-1 */
  for(i=(n-1)/2 ;i>=1; i--)
    FixIntHeap(a,n-1,i);

  /*Consume heap up*/
  for(i=n-1;i>=2;i--)
  {
    temp=a[i];
    a[i]=a[1];
    a[1]=temp;
    FixIntHeap(a,i-1,1);
  }

  /*The sorted range is from 1 to n-1.By placing a[0] to a proper place,
  We complete the sorting (ranging from 0 to n-1)*/
  temp=a[0];
  i=0;
  while(a[i+1]<temp && i+1<n)
  {
    a[i]=a[i+1];
    i++;
  }

  a[i]=temp;
}