背景
接上面两篇文章
算法踩坑-快速排序
算法踩坑2-插入排序
来继续聊聊最近我写的一些算法的小例程，这次要聊的是堆排序，是一个时间复杂度为NLogN的算法。
主要从以下几方面来说的：
- 堆排序思想
- 堆排序实现
- 堆排序优化
堆排序思想
堆排序是基于优先队列的最大堆或者是最小堆实现的，每次删除最大堆的顶部元素，然后通过LogN的时间来恢复最大堆的属性，循环这个步骤，最终得到一个有序的序列来达到排序的目的。
堆排序实现
堆的初始化
PriorityQueue PQ_Initialize(int MaxElements) {
PriorityQueue H = NULL;
if (MaxElements < MinPQSize) {
err(1, "队列长度小于最小值10");
}
H = malloc(sizeof(struct HeapStruct));
if (NULL == H) {
err(1, "Out of space");
}
H->Elements = malloc((MaxElements + 1) * sizeof(ElementType));
if (NULL == H->Elements) {
err(1, "Out of space");
}
H->Capacity = MaxElements;
H->Size = 0;
H->Elements[0] = MinData;
return H;
}
堆的插入
void PQ_InsertToMinQueue(ElementType x,PriorityQueue H) {
if (PQ_IsFull(H)) {
err(1, "队列满，不可插入数据");
}
// 最小堆，上虑操作
int i;
for (i = ++H->Size; H->Elements[i/2] > x; i /= 2) {
H->Elements[i] = H->Elements[i/2];
}
H->Elements[i] = x;
}
堆的删除
ElementType PQ_DeleteMin(PriorityQueue H) {
if (PQ_IsEmpty(H)) {
err(1, "Empty");
}
ElementType MinElem = H->Elements[1];
// 最小堆，最后一个元素放在顶部，下虑操作
ElementType lastElement = H->Elements[H->Size--];
int i;
int child;
for (i = 1; i * 2<=H->Size; i=child) {
// 找到孩子节点中小的往上移动
child = i * 2;
if (child+1 <= H->Size && H->Elements[child+1] < H->Elements[child] ) {
child += 1;
}
if (child <= H->Size && H->Elements[child] < lastElement) {
H->Elements[i] = H->Elements[child];
} else {
break;
}
}
// 放到指定位置
H->Elements[i] = lastElement;
// 最小元素放在最后，
// 使用堆排序的时候不用增加额外的空间保存排序后的数据，排序后的数据是倒叙的
H->Elements[H->Size+1] = MinElem;
return MinElem;
}
堆排序优化
使用一般的方式进行堆排序，需要额外的增加O(N)的内存开销，在删除顶部元素，并且把最后一个元素归为的时候，最后一个位置刚好是空出来的，所以可以把删除的元素放入最后的位置就不需要增加O(N)的内存开销，达到了空间优化的目的。
// 放到指定位置
H->Elements[i] = lastElement;
// 最小元素放在最后，
// 使用堆排序的时候不用增加额外的空间保存排序后的数据，排序后的数据是倒叙的
H->Elements[H->Size+1] = MinElem;
