1 #include <iostream>
2 using namespace std;
3
4 class suanfa {
5 public:
6 int tempsize;
7 suanfa(int heapsize);
8 /*將a[i]為根節(jié)點(diǎn)的子樹(shù)生成最大堆!*/
9 void heapify(int* a, int i);
10 /*獲取父節(jié)點(diǎn),在這里沒(méi)用*/
11 int parent(int i);
12 /*獲取左子樹(shù),數(shù)組序號(hào)*/
13 int left(int i);
14 /*獲取右子樹(shù),數(shù)組序號(hào)*/
15 int right(int i);
16 /*交換2個(gè)值*/
17 void swap(int *a ,int i, int j);
18 /*暫時(shí)先不用--日后再用*/
19 void max_heapify(int* a, int heapsize);
20 /*堆排序*/
21 void heapify_sort(int* a, int size);
22 ~suanfa();
23 };
24 suanfa::suanfa(int heapsize){
25 tempsize = heapsize;
26 }
27 int suanfa::left(int i){
28 return 2*i + 1;
29 }
30 int suanfa::right(int i){
31 return 2*i+2;
32 }
33 int suanfa::parent(int i){
34 return i/2;
35 }
36
37 suanfa::~suanfa(){
38 //delete [] a;
39 //m_array = NULL;
40 cout << "我被析構(gòu)了" << endl;
41 }
42 void suanfa::heapify(int* a, int i){
43 int l = left(i);
44 int r = right(i);
45 int largest = 0;//以a[i]為根節(jié)點(diǎn)的子樹(shù)的最大值的數(shù)組下標(biāo)
46 int size = tempsize;//heapsize 這里=數(shù)組的大小
47 /**獲取該子樹(shù)最大下標(biāo)*/
48 if (l > size -1) {
49 l = size -1;
50 }
51 if(r > size -1){
52 r = size -1;
53 }
54 if (l <= size - 1 && a[l] > a[i]) {
55 largest = l;
56 }else {
57 largest = r;
58 }
59 if (r <= size - 1 && a[r] > a[largest]) {
60 largest = r;
61 }
62 /*如果根節(jié)點(diǎn)不是改子數(shù)組最大值,則進(jìn)行交換*/
63 if (a[i] < a[largest]) {
64 swap(a, i, largest);
65 heapify(a, largest);
66 }
67
68
69 }
70 void suanfa::swap(int* a, int i, int j){
71 int key = a[i];
72 a[i] = a[j];
73 a[j] = key;
74 }
75 void suanfa::max_heapify(int* a, int heapsize){
76 //j->(heapsize-1)/2的子數(shù)組是最大堆.
77 for(int j = (heapsize - 1) / 2; j >=0; --j)
78 {
79 heapify(a,j);
80 }
81 }
82 void suanfa::heapify_sort(int* a, int size){
83 max_heapify(a, size);
84 for (int i = size -1; i>0; i--) {
85 swap(a, 0, i);
86 tempsize --;
87 max_heapify(a, tempsize);
88 }
89 }
90 int main () {
91
92 //int a[] = {16,4,10,14};
93 int a[10000];
94 for (int i=0; i<10000; i++) {
95 a[i] = i;
96 }
97 int size = sizeof a / sizeof a[0];
98 suanfa sf(size);
99 //sf.heapify_sort(a, size);
100 //sf.heapify(a, 2);
101 sf.max_heapify(a, size);
102 for (int i=0; i<size; i++) {
103 cout << a[i] << " ";
104 }
105 cout << endl;
106 return 0;
107 }
108