1 /*************************************************************************
2 > File Name: HeapSort.cpp
3 > Author: zhoukang
4 > Mail: zhoukang199191@126.com
5 > Created Time: 2014年08月11日 星期一 22时36分38秒
6 ************************************************************************/
7
8 #include <iostream>
9 #include <vector>
10 #include <algorithm>
11 using namespace std;
12
13 void max_heapfy(vector<int> & A,int index,int heapsize)
14 {
15 int l = 2*index+1;
16 int r = 2*index+2;
17
18 int largest = index;
19 if(l <= heapsize && A[l] > A[index])
20 largest = l;
21 if(r <= heapsize && A[r] > A[largest])
22 largest = r;
23 if(largest != index)
24 {
25 swap(A[index],A[largest]);
26 max_heapfy(A,largest,heapsize);
27 }
28 }
29
30 void build_max_heap(vector<int> &A,int heapsize)
31 {
32 // assert(heapsize >= 0);
33 int i;
34 for(i = heapsize/2-1 ; i >= 0 ; --i)
35 max_heapfy(A,i,heapsize);
36 }
37
38 void heap_sort(vector<int> &A,int heapsize)
39 {
40 build_max_heap(A,heapsize);
41 int i;
42 for(i = heapsize-1; i > 0 ; --i )
43 {
44 swap(A[0],A[i]);
45 max_heapfy(A,0,i);
46 }
47 }
48
49 int main()
50 {
51 cout<<"before"<<endl;
52 vector<int> A;
53 A.push_back(3);
54 A.push_back(1);
55 A.push_back(2);
56 heap_sort(A,3);
57 }
