【算法】（C语言）：堆排序

堆（二叉树的应用）：

完全二叉树。
最大堆：每个节点比子树所有节点的数值都大，根节点是最大值。
父子索引号关系（根节点为0）：（向上）子节点x，父节点(x-1) // 2。（向下）父节点x，左子节点2x+1，右子节点2x+2。
一般用数组实现堆。

堆排序：

第一步、构建堆（最大堆）。

找到最后的父节点：(最后元素的索引号-1) // 2。
从最后的父节点到根节点，依次向下调整（比较父节点和左右子节点，最大值为父节点）。
最终，根节点为最大值。尾指针指向最后节点。

第二步、排序

交换根节点和尾指针所在节点。此时，尾指针所在节点为目前正在排序中数据的最大值，保持不动。
尾指针向前（向左）移动一位。
从根节点到尾指针所在节点，依次向下调整。
此时，根节点为目前正在排序中数据的最大值（不包含已排序好且保持不动的最大值）。

第三步、重复第二步，直到尾指针指向根节点停止。

时间复杂度：O(nlogn)

初次构建堆，时间约n。
每次向下调整，都是使用2x+1、2x+2，遍历次数是logn（对数），几乎每个元素都要重排，因此时间约 nlogn。
相对于nlogn而言，n可忽略，即总时间O(nlogn)。

空间复杂度：O(1)

在原位置排序，只重复使用了用于交换的临时空间，不随数据量的变动而变动，空间使用为常量(1)。

C语言实现思路：

先构建堆（最大堆），再排序。

void heapsort(int *array, int length)		// heap sort
{
	// 构建堆（最大堆）
    // 找到最后的父节点
	int i = ceil((length - 1) / 2);	
    // 从最后的父节点到根节点，依次向下调整（父子节点比较大小，最大值为父节点）
	for(; i >= 0; i--)
	{
		adjustdown(array, i, length - 1);
	}
	
	// 排序
    // 交换根节点和尾指针所在节点，尾指针前移一位，从根节点开始向下调整
	for(int n = length - 1; n > 0; n--)
	{
		swap(&array[0], &array[n]);
		adjustdown(array, 0, n - 1);
	}
}

因多次向下调整，多次交换两个数据，因此，向下调整、交换数据分别用函数单独实现。

交换两个数据：

传入的参数为数据的内存地址，将直接在内存地址进行数据交换。

void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

向下调整：

向下在左右子节点中找到较大值的节点，父节点再与较大值的子节点比较大小，若子节点数值更大，父子节点交换位置。

void adjustdown(int *array, int start, int end)		// adjust the heap down
{
	while(start < end)
	{
		int left = 2 * start + 1, right = 2 * start + 2, maxchild;
		// 比较左右子节点，找到较大值的子节点
		if(left > end) break;
		if(right <= end && array[left] < array[right]) maxchild = right;
		else maxchild = left;
		// 与较大值的子节点比较，若子节点数值更大，交换父子节点的位置
		if(array[start] < array[maxchild])
		{
			swap(&array[start], &array[maxchild]);
			start = maxchild;
		}
		else break;
	}
}

完整代码：（heapsort.c）

#include <stdio.h>
#include <math.h>

/* function prototype */
void heapsort(int *, int);	// heap sort
void traverse(int *, int);	// show element one by one

/* main function */
int main(void)
{
	int arr[] = {4,2,6,9,5,1,3};
	int n = sizeof(arr) / sizeof(int);
	traverse(arr, n);

	heapsort(arr, n);	
	printf("[ after heap sort ] ");
	traverse(arr, n);
	return 0;
}

/* subfunction */
void swap(int *a, int *b)		// change the value of two datas
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void adjustdown(int *array, int start, int end)		// adjust the heap down
{
	while(start < end)
	{
		int left = 2 * start + 1, right = 2 * start + 2, maxchild;
		// left child or right child, find the max one
		if(left > end) break;
		if(right <= end && array[left] < array[right]) maxchild = right;
		else maxchild = left;
		// parent compair with maxchild, if smaller than maxchild,change the position
		if(array[start] < array[maxchild])
		{
			swap(&array[start], &array[maxchild]);
			start = maxchild;
		}
		else break;
	}
}

void heapsort(int *array, int length)		// heap sort
{
	// build a heap
	int i = ceil((length - 1) / 2);			// find the last parent
	// from the last parent to 0 index, cycle ajust the heap down(parent compair with child)
	for(; i >= 0; i--)
	{
		adjustdown(array, i, length - 1);
	}
	
	// sort (root is max, change max to the last, end pointer move a step to the left)
	for(int n = length - 1; n > 0; n--)
	{
		// swap the first and last element
		swap(&array[0], &array[n]);
		// from 0 index, compair with left child and right child, max is parent
		adjustdown(array, 0, n - 1);
	}
}

void traverse(int *array, int length)		// show element one by one
{
	printf("elements(%d): ", length);
	for(int k = 0; k < length; k++)
	{
		printf("%d  ", array[k]);
	}
	printf("\n");
}