数组堆排序

堆排序也是一种空间换时间的做法，速度相对较快，我们需要生成一个动态的临时数组，以二叉堆的格式将数据插入到数组中，表现形式如下图：

这个二叉堆是一个完全二叉树或一个近似完全的二叉树，要满足以下两点特性：

【二叉堆概念】

• 父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
• 每个节点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）

【最大堆最小堆概念】

• 父节点的键值总是大于或等于子节点的键值时为最大堆（大顶堆）
• 父节点的键值总是小于或等于子节点的键值时为最小堆（小顶堆）

---

了解以上概念后，我们就要清楚堆排序的过程了，首先我们要将数据按一定格式（比如按大顶堆或者小顶堆的格式）插入到二叉堆中，在插入过程中要对数据进行对比排序。全部插入完成后，将二叉堆中的根节点的数值依次取出，取出的同时，将堆中最后一个数据覆盖到根节点，再将这个数据与所有子节点对比，最终把最大（或最小）的子节点移动到根节点的位置。这样保证每次取出的数据都是最大（或最小）的数据。表现形式如下：

【插入元素】

插入元素的步骤

1. 先将此元素插入添加到完全二叉树的最后面的位置(数组的最后), 此完全二叉树多了一个叶子节点.
2. 求出此叶子节点的父节点, 与其父节点进行比较, 如果比父节点大则二者交换位置
3. 重复步骤2
4. 节点插入完成

【弹出元素】

弹出元素步骤

1. 删除根节点
2. 将最后一个叶子节点放到根节点的位置
3. 新的根节点分别与其左右孩子比较,如果比根节点大, 选出较大的一个
4. 将根节点与值较大的叶子节点交换位置
5. 发生交换的孩子节点如果还有子节点, 重复3, 4步

【实现代码】

#include <stdio.h>
#include <stdlib.h>

typedef struct _tag_heapTag
{
// 指向数据的指针，用于创建动态数组存储数据
int *arrList;
// 记录当前堆中的节点个数
int nSize;
}MyHeap;

int PopMaxValue(MyHeap* pHeap)
{
int nPos = 1;
// 记录根节点最大值，用于返回值
int nMax = pHeap->arrList[nPos];
// 把数组最后的值挪动到根节点的位置，并记录下挪动过来的值
int nTemp = pHeap->arrList[nPos] = pHeap->arrList[pHeap->nSize];

// 得到根节点的子节点的位置
int nChild = nPos * 2;
while (nChild <= pHeap->nSize)
{
// 判断右子节点的下标不超过数组长度
if (nChild + 1 <= pHeap->nSize &&
// 判断右子节点是否大于左子节点
pHeap->arrList[nChild] < pHeap->arrList[nChild + 1])
{
// 如果右子节点大于左子节点，那么让子节点位置等于右子节点
nChild++;
}
// 根节点的值是最大的，无需交换了
if (pHeap->arrList[nPos] > pHeap->arrList[nChild])
break;

// 如果小于，那么交换子节点和当前根节点的值
pHeap->arrList[nPos] = pHeap->arrList[nChild];
// 让根节点等于被交换前原子节点的位置
nPos = nChild;
// 计算出交换后节点位置下的子节点的位置，用于下次循环
nChild *= 2;
}

// 退出循环后nPos的位置一定是最下面叶子节点的位置，把之前备份的值赋值给它
pHeap->arrList[nPos] = nTemp;
// 数组长度–
pHeap->nSize–;

// 返回被删除的数据
return nMax;
}

int InsertKey(MyHeap* pHeap, int nPos)
{
while (nPos > 1)
{
// 记录下当前nPos节点值
int nMax = pHeap->arrList[nPos];
// 父节点下标
int nParent = nPos / 2;
if (nMax > pHeap->arrList[nParent])
{
// 交换子节点和父节点的值
pHeap->arrList[nPos] = pHeap->arrList[nParent];
pHeap->arrList[nParent] = nMax;
// 记录父节点的位置给nPos，用于下次循环
nPos = nParent;
}
else
{
// 子节点已经不大于父节点的值
break;
}
}
return 0;
}

void Insert(MyHeap* pHeap, int nData)
{
pHeap->nSize++;
pHeap->arrList[pHeap->nSize] = nData;
// 比较，向上渗透
InsertKey(pHeap, pHeap->nSize);
}

void heapSort(int arr[], int len)
{
MyHeap myHeap;
// 给插入数据的数组空间分配内存，因为要跳过下标为0的元素
// 所以长度要是传递进来的数组长度 + 1的大小
myHeap.arrList = (int*)malloc(sizeof(int) * (len + 1));
myHeap.nSize = 0;

for (int i = 1; i <= len; i++)
{
// 一次将数组中的元素插入动态分配的数组
Insert(&myHeap, arr[i - 1]);
}

// 弹出数据并打印弹出的值
for (int i = 1; i <= len; i++)
{
printf(“%d “, PopMaxValue(&myHeap));
}
// 释放申请的空间
free(myHeap.arrList);
}

int main(int argc, char* argv[])
{
int arr[] = { 12, 5, 33, 6, 10 };
int len = sizeof(arr) / sizeof(int);
printf(“待排序数组序列: “);
for (int i = 0; i < len; ++i)
{
printf(“%d\t”, arr[i]);
}
putchar(10);

//遍历
printf(“堆排序之后的序列: “);
heapSort(arr, len);
putchar(10);
return 0;
}