Heap sort

Implement sorting with heap.

C++:
01 bool MyHeap::insert(int x)
02 {
03     if(isFull())
04         return false;
05     A[tail++]=x;
06     int tmp=tail1;
07     while(tmp>0){
08         if(A[tmp/2]>A[tmp])
09             swap(A[tmp/2],A[tmp]);
10         tmp=tmp/2;
11     }
12 }
13 
14 void HeapifyDown(int A[], int size, int i){
15     if(2*i>=size)
16         return;
17     int j;
18     if(2*i<size){
19         int left=2*i;
20         int right=2*i+1;
21         j=A[left]<=A[right]?left:right;
22     }else
23         j=2*i;
24     if(A[j]<A[i]){
25         swap(A[i],A[j]);
26         HeapifyDown(A,size,j);
27     }
28 }
29 
30 int MyHeap::getMin()
31 {
32     if(tail==0)
33         return 1;
34     int result=A[0];
35     A[0]=A[tail];
36     HeapifyDown(A,tail,0);
37     return result;
38 }
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s