浙江财经大学
信息管理与工程学院

堆排序

本文由 Ocrosoft 于 2016-12-26 16:22:22 发表
#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;
}

欢迎转载,请保留出处与链接。Ocrosoft » 堆排序

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址