﻿堆排序-Ocrosoft

# 堆排序

```#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
#define rep(a,v,b) for(int a=v;a<b;a++)
#define repe(a,v,b) for(int a=v;a<=b;a++)
#define pre(a,v,b) for(int a=v;a>b;a--)
#define pree(a,v,b) for(int a=v;a>=b;a--)
#define lowbit(x) x&-x
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 27 + 10;
const int MOD = 1000000007;
int gcd(int a, int b)
{
if (!b)return a;
return gcd(b, a%b);
}
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
/*(◕‿‿◕) 签订契约,成为马猴烧酒吧 (◕‿‿◕)*/
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
using namespace std;
void MinHeapFixdown(int a[], int i, int n)
{
int j, temp;

temp = a[i];
j = 2 * i + 1;
while (j < n)
{
if (j + 1 < n && a[j + 1] < a[j]) //在左右孩子中找最小的
j++;

if (a[j] >= temp)
break;

a[i] = a[j];//把较小的子结点往上移动,替换它的父结点
i = j;
j = 2 * i + 1;
}
a[i] = temp;
}
void MakeMinHeap(int a[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
MinHeapFixdown(a, i, n);
}
void MinheapsortTodescendarray(int a[], int n)
{
for (int i = n - 1; i >= 1; i--)
{
swap(a[i], a[0]);
MinHeapFixdown(a, 0, i);
}
}
int main()
{
int a[] = { 9,12,17,30,50,20,60,65,4,49 };
int b[] = { 9,12,17,30,50,20,60,65,4,49 };
MakeMinHeap(a, 10);
make_heap(b, b + 10, greater<int>());
MinheapsortTodescendarray(a, 10);
sort_heap(b, b + 10, greater<int>());
for (int i = 0; i < 10;i++)
printf("%d ",a[i]);
printf("\n");
for (int i = 0; i < 10; i++)
printf("%d ", b[i]);
printf("\n");
return 0;
}```