堆排序模版

 1 #include
 2 #include
 3 using namespace std;
 4 
 5 int a[100010];
 6 int lengtha;
 7 void heapify(int a[], int i)
 8 {
 9     int l = i * 2, r = i * 2 + 1, maxx = i;
10     if (l <= lengtha && a[l] > a[i])
11     {
12         maxx = l;
13     }
14     else{
15         maxx = i;
16     }
17     if (r <= lengtha && a[r] > a[maxx])
18     {
19         maxx = r;
20     }
21     if (maxx != i)
22     {
23         swap(a[i], a[maxx]);
24         heapify(a, maxx);
25     }
26 }
27 void build_heap(int a[])
28 {
29     for (int i = floor(lengtha/2); i >= 1; i--)
30     {
31         heapify(a, i);
32     }
33 }
34 void heap_sort(int a[])
35 {
36     build_heap(a);
37     for (int i = lengtha; i >= 2; i--)
38     {
39         swap(a[1], a[i]);
40         lengtha--;
41         heapify(a, 1);
42     }
43 }
44 int main()
45 {
46 
47     int n;
48     cin >> n;
49     for (int i = 1; i <= n; i++)
50     {
51         cin >> a[i];
52     }
53     lengtha = n;
54     heap_sort(a);
55     for (int i = 1; i <= n; i++)
56     {
57         cout << a[i] << " ";
58     }
59     return 0;
60 }