堆排序-----HeapSort

1. 完全二叉树

上图，就是一个完全二叉树，其特点在于：

从作为第一层的根开始，除了最后一层之外，第N层的元素个数都必须是2的N次方；第一层2个元素，第二层4个，第三层8个，以此类推。
而最后一行的元素，都要紧贴在左边，换句话说，每一行的元素都从最左边开始安放（生成的顺序是从上往下，从左往右），两个元素之间不能有空闲，具备了这两个特点的树，就是一棵完全二叉树。

2.小根堆

我们假设有一棵完全二叉树，在满足作为完全二叉树的基础上，对于任意一个拥有父节点的子节点，其数值均不小于父节点的值；这样层层递推，就是根节点的值最小，这样的树，称为小根堆。
3.大根堆

同理，又有一棵完全二叉树，对于任意一个子节点来说，均不大于其父节点的值，如此递推，就是根节点的值是最大的，这样的数，称为大根堆。

如上图，左边就是大根堆；右边则是小根堆，这里必须要注意一点，只要求子节点与父节点的关系，两个节点的大小关系与其左右位置没有任何关系。

明确下大根堆，小根堆的概念，继续说堆排序。
4. 堆排序

现在对于堆排序来说，我们先要做的是，把待排序的一堆无序的数，整理成一个大根堆，或者小根堆，下面讨论以大根堆为例子。

给定一个列表array=[16,7,3,20,17,8]，对其进行堆排序（使用大根堆）。

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

a.假设给定无序序列结构如下

2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

此处必须注意，我们把6和9比较交换之后，必须考量9这个节点对于其子节点会不会产生任何影响？因为其是叶子节点，所以不加考虑；但是，一定要熟练这种思维，写代码的时候就比较容易理解为什么会出现一次非常重要的交换了。

4.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

牢记上面说的规则，每次交换都要把改变了的那个节点所在的树重新判定一下，这里就用上了，4和9交换了，变动了的那棵子树就必须重新调整，一直调整到符合大根堆的规则为截。

此时，我们就将一个无序序列构造成了一个大顶堆。

步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

a.将堆顶元素9和末尾元素4进行交换

这里，必须说明一下，所谓的交换，实际上就是把最大值从树里面拿掉了，剩下参与到排序的树，其实只有总结点的个数减去拿掉的节点个数了。所以图中用的是虚线。

b.重新调整结构，使其继续满足堆定义

c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

#include <stdio.h>

#define Left  2*RootId + 1
#define Right 2*RootId + 2

void AdJust(int arr[],int len,int RootId)
{
	while (1)
	{
		//两个孩子
		if(Right < len)
		{ 
			//左孩子大于右孩子
			if(arr[Left] > arr[Right])
			{
				//大的和父亲比较
				if(arr[Left] > arr[RootId])
				{
					arr[Left] = arr[Left]^arr[RootId];
					arr[RootId] = arr[Left]^arr[RootId];
					arr[Left] = arr[Left]^arr[RootId];

					RootId = Left;
					continue;
				}
				break;
			}
			//右孩子大于左孩子
			else
			{
				if(arr[Right] > arr[RootId])
				{
					arr[Right] = arr[Right]^arr[RootId];
					arr[RootId] = arr[Right]^arr[RootId];
					arr[Right] = arr[Right]^arr[RootId];

					RootId = Right;
					continue;
				}
				break;
			}
		}
		//一个孩子
		else if(Left < len)
		{
			if(arr[Left] > arr[RootId])
			{
				arr[Left] = arr[Left]^arr[RootId];
				arr[RootId] = arr[Left]^arr[RootId];
				arr[Left] = arr[Left]^arr[RootId];

				RootId = Left;
				continue;
			}
			break;
		}
		//没孩子
		else
		{
			break;
		}
	}
}
void HeapSort(int arr[],int len)
{
	int i;
	if(arr == NULL || len <= 0)
		return;
	//1.初始堆---大堆
	for(i = len /2 -1 ;i>=0 ;i--)
	{
		AdJust(arr,len,i);
	}
	//2.排序
	for(i = len-1;i>0;i--)
	{
		//交换
		arr[i] = arr[i]^arr[0];
		arr[0] = arr[i]^arr[0];
		arr[i] = arr[i]^arr[0];
		//调整栈顶
		AdJust(arr,i,0);
	}

}

void Print(int arr[],int len)
{
	for(int i = 0;i<len;i++)
	{
		printf("%d ",arr[i]);
	}
}
int main()
{
	int arr[] = {2,19,7,11,14,3,6,8,1};
	HeapSort(arr,sizeof(arr)/sizeof(arr[0]));
	Print(arr,sizeof(arr)/sizeof(arr[0]));
	return 0;
}

补充：
1.使用一维数组存储，可以方便的找到任意节点的值。从0开始。
2. 知道第i个节点：
父节点：(i-1)/2
子节点：c1=2i+1
子节点：c2=2i+2