堆排序

堆排序:
堆定义:分大顶堆和小顶堆 大顶堆的父结点值比子结点大,并且左节点的值大于右结点的值，它可被视为一颗完全二叉树 树的深度为n 则 n-1层以前是被填满的,最后一层从一个结点的左子树开始填和数组对应
如数组 {0, 3, 5, 1, 8, 10, 9} number[0]不在排列范围内 下标从1开始,此时的堆结构为如图:

当用数组表示存贮了n个元素的堆时,叶子结点的下标从 n/2+1, n/2+2.....n
证明:当此为满二叉树的时候 且树的深度为k 则总共有 2^(k) - 1个结点，
由此可得前k-1层有2^(k - 1) - 1个结点
而总共有n个结点 则最后一层的结点树为 n - 2^(k - 1)+1个结点
而则它的父节点有
[n - 2^(k -1) + 1] / 2 (n-2^(k-1)-1为偶数时)个父结点
[n - 2^(k -1) + 1] / 2 + 1(为奇数时)
而倒数第二层有 2 ^(k-2)个结点
则倒数第二层存在的叶子结点为 2^(k - 2) - [n - 2^(k -1) + 1]/ 2个结点（偶数）
则叶子结点的起始点为n -  [ n - 2^(k - 1)-1] - 2^(k - 2) + [n - 2^(k -1) - 1]/ 2= (n +1)/ 2  + 1取整 为 n / 2 + 1
实现代码(大顶堆):

#include <stdio.h>
/*堆排序 堆数据结构是一种数组对象
*可以被视为一颗完全二叉树、树中每个节点的值与数组中存放该节点的值对应
*大顶堆 父结点的值大于孩子结点
*/
//调整堆
int num[] = {0, 3, 5, 1, 8, 10, 9};
int *number = num;
void MAX_HEAPIFY(int i, int length)
{
	int left = i << 1;  //因为i接点的左孩子是 2 * i ,右孩子是 2 * i + 1
	int right = left + 1;
	int largest = i;
	if(left <= length && number[i] < number[left])  //比较左孩子结点和父节点值的大小 ,并用计数器记下位置 largest
	{
		largest = left;
	}

	if(right <= length && number[right] > number[largest]) //比较右孩子和 largest的大小、如果largest=left 然后比较number[left] 和number[rigth]的大小把 大的向上调
	{
		largest = right;
	}
	if(largest != i)  //如果largest == i表明子树符合大顶堆的性质,则返回
	{
		number[i] = number[largest] + number[i];
		number[largest] = number[i] - number[largest];  
		number[i] = number[i] - number[largest];
		MAX_HEAPIFY(largest, length);  //largest = 2
	}
	
}
//建立大顶堆
void BULD_MAX_HEAP(int length)
{
	int i;
	for(i = length / 2; i > 0; i--)
	{
		MAX_HEAPIFY(i, length);  //从 length / 2 开始 从下向上依次调整大顶堆 叶子结点从 [length / 2](向下取整) + 1 ~ length
	}
}

void HEAPSORT(int length)
{
	BULD_MAX_HEAP(length);
	for(int i = length; i >= 2; i--)
	{
		number[1] = number[1] + number[i];
		number[i] = number[1] - number[i];
		number[1] = number[1] - number[i];  //交换值 ，因为堆顶是最大的
		length--;
		MAX_HEAPIFY(1, length);
	}
}
int main()
{
	int length = sizeof(num) / sizeof(int); //计算数组长度
	HEAPSORT(length - 1);
	for(int i = 1; i < length; i++)
	{
		printf("%d ", number[i]);  //输出大顶堆
	}
	printf("\n");
	return 0;
}

建立小顶堆:

void MIN_HEAPIFY(int i, int length)
{
	int left = i << 1;
	int right = left + 1;
	int small = i;
	if(left <= length && number[left] < number[i])
	{
		small = left;
	}
	if(right <= length && number[right] < number[small])
	{
		small = right;
	}
	if(small != i)
	{
		number[i] = number[small] + number[i];  
        number[small] = number[i] - number[small];    
        number[i] = number[i] - number[small];  
        MIN_HEAPIFY(small, length);  //largest = 2  
	}
}

其余代码和上面不变,输出序列是降序的