位置堆排序[置顶] 堆的构建与堆排序

废话就不多说了，开始。。。

堆是一种经常使用数据结构，我们在编写算法的时候，会经常使用他，为了懂得这种数据结构，我自己学着实现了一下，几个基本操作，返回父节点的位置，左儿子节点的位置，右儿子节点的位置，调整堆，该方法是堆中最重要的操作方法！建立堆，堆排序都是以这个操作方法为核心的，重点说明下这个方法:

输入为数组A[],位置i，

1。先获得他的两个儿子的位置，

2. 判断儿子和父亲谁大，

3.若儿子比父亲大，则交换儿子和父亲的位置！

4.并继续递归调整被交换过儿子的位置！

class MyHeap
{
public:
	MyHeap();
	~MyHeap();
	int Parent(int i);
	int Left(int i);
	int Right(int i);

	void Max_HeapPIFy(int A[],int i);

	int exchange(int A[],int i,int largest);

	
	int size;

	int BuildMaxHeap(int A[],int n);

	void HeapSort(int A[],int n);
private:

};

MyHeap::MyHeap()
{
	
}

MyHeap::~MyHeap()
{
	
}

int MyHeap::Parent(int i)
{
	return i/2;
}

int MyHeap::Left(int i)
{
	return 2*(i+1)-1;
}

int MyHeap::Right(int i)
{
	return 2*(i+1);
}

void MyHeap::Max_HeapPIFy(int A[],int i)
{
	int l = Left(i);
	int r = Right(i);

	int largest ;

	if (l<size&&A[l]>A[i])
	{
		largest = l;
	}
	else
	{
		largest = i;
	}
	if (r<size&&A[r]>A[largest])
	{
		largest = r;
	}
	
	if (largest!=i)
	{
		exchange(A,i,largest);
		Max_HeapPIFy(A,largest);
	}
	
}

int MyHeap::exchange(int A[],int i,int j)
{
	int temp	= A[i];
	A[i]		= A[j];
	A[j]	= temp;
	return 0;
}

int MyHeap::BuildMaxHeap(int A[],int n)
{
	size = n;

	for (int i = (n)/2; i>=0; i--)
	{
		Max_HeapPIFy(A,i);
	}
	return 0;
}

void MyHeap::HeapSort(int A[],int n)
{
	BuildMaxHeap(A,n);

	for (int i = size-1; i>0; i--)
	{
		exchange(A,0,i);
		size -=1;
		Max_HeapPIFy(A,0);
	}
	
}

每日一道理
美丽是平凡的，平凡得让你感觉不到她的存在；美丽是平淡的，平淡得只剩下温馨的回忆；美丽又是平静的，平静得只有你费尽心思才能激起她的涟漪。

int A[10]={2,3,4,5,6,7,8,9,0,1};

	MyHeap m_heap;

	m_heap.BuildMaxHeap(A,10);
	for (int i = 0; i <10; i++)
	{
		cout<<A[i]<<"\t";
	}
	cout <<endl;
	m_heap.HeapSort(A,10);
	
	for (int i = 0; i <10; i++)
	{
		cout<<A[i]<<"\t";
	}
	cout <<endl;

文章结束给大家分享下程序员的一些笑话语录：大家喝的是啤酒，这时你入座了。
你给自己倒了杯可乐，这叫低配置。
你给自已倒了杯啤酒，这叫标准配置。
你给自己倒了杯茶水，这茶的颜色还跟啤酒一样，这叫木马。
你给自己倒了杯可乐，还滴了几滴醋，不仅颜色跟啤酒一样，而且不冒热气还有泡泡，这叫超级木马。
你的同事给你倒了杯白酒，这叫推荐配置。
菜过三巡，你就不跟他们客气了。
你向对面的人敬酒，这叫p2p。
你向对面的人敬酒，他回敬你，你又再敬他……，这叫tcp。
你向一桌人挨个敬酒，这叫令牌环。
你说只要是兄弟就干了这杯，这叫广播。
有一个人过来向这桌敬酒，你说不行你先过了我这关，这叫防火墙。
你的小弟们过来敬你酒，这叫一对多。
你是boss，所有人过来敬你酒，这叫服务器。
酒是一样的，可是喝酒的人是不同的。
你越喝脸越红，这叫频繁分配释放资源。
你越喝脸越白，这叫资源不释放。
你已经醉了，却说我还能喝，叫做资源额度不足。
你明明能喝，却说我已经醉了，叫做资源保留。
喝酒喝到最后的结果都一样
你突然跑向厕所，这叫捕获异常。
你在厕所吐了，反而觉得状态不错，这叫清空内存。
你在台面上吐了，觉得很惭愧，这叫程序异常。
你在boss面前吐了，觉得很害怕，这叫系统崩溃。
你吐到了boss身上，只能索性晕倒了，这叫硬件休克。

--------------------------------- 原创文章 By
位置和堆排序
---------------------------------