힙 정렬(HEAP SORT)

// win4.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

#include "stdafx.h"
#include<iostream>
#include<iomanip>
using namespace std;

class CWATHeapSort
 { 
 private: 
  int *x; 
  int items; 
 public: 
  CWATHeapSort(int); 
  ~CWATHeapSort(); 
  void input(int []); 
  void heap_property(int,int); 
  void construct_heap(); 
  void display(); 
  void sort(int []);
 };

CWATHeapSort::CWATHeapSort(int n)
 { 
 items=n; 
 x=new int[items+1];
 }

CWATHeapSort::~CWATHeapSort()
 { 
 delete [] x;
 }

void CWATHeapSort::input(int a[])
 { 
 for(int i=0;i<=items;i++) 
  x[i]=a[i-1];
 }

void CWATHeapSort::display()
 { 
 cout<<"\n Sorted elements are :"; 
 for(int i=1;i<=items;i++) 
  cout<<setw(5)<<x[i];
 }

void CWATHeapSort::construct_heap()
 { 
 for(int i=items/2;i>0;i--) 
  heap_property(i,items);
 }

void CWATHeapSort::heap_property(int root, int limit)
 { 
 int done=0; 
 int big=x[root]; 
 int j=2*root; 
 while((j<=limit) && (done==0)) 
  { 

  if((j<limit) && (x[j]<x[j+1])) 
   j++; 
  if(big >=x[j]) 
   done=1; 
  else 
   { 
   x[j/2]=x[j]; 
   j=2*j; 
   } 
  } 
 x[j/2]=big;
 }

void CWATHeapSort::sort(int a[])
 { 
 construct_heap(); 
 for(int i=(items-1);i>0;i--) 
  { 
  int temp; 
  temp=x[i+1]; 
  x[i+1]=x[1]; 
  x[1]=temp; 
  a[i]=x[i+1]; 
  heap_property(1,i); 
  } 
 a[0]=x[1];
 }

int main()
{ 
 int a[100]={1,2,3,4,7,9,44,33,22,55,77,88,};      
 int n=12; 

 CWATHeapSort obj(n); 
 obj.input(a); 
 obj.sort(a); 
 obj.display(); 
 return 0;
}

<결과>

 Sorted elements are :    1    2    3    4    7    9   22   33   44   55   77 88