1.堆及其性质
堆是使用数组实现二叉树的顺序结构，数组存储只适用于完全二叉树
- 堆总是一颗完全二叉树
- 堆中的某个结点的值总是不大于(小堆)或不小于(大堆)其子结点的值（左右子节点间的关系不一定）
- 堆从上至下是递增(递减)的，但从左至右不一定有序
下图为一个大堆
父子结点下标的对应关系
parent = (child - 1) / 2leftchild = 2 * parent + 1rightchild = 2 * parent + 2
2.堆的实现
向堆插入数据
在尾部插入数据，再进行向上调整，不满足堆的规则就交换，满足就停止（循环至堆顶）
void HeapPush(Heap* ph, HPDataType x)
{
assert(ph);
//如果堆已满，则扩容
if (ph->size == ph->capacity)
{
HPDataType* tmp = (HPDataType*)realloc(ph->a, sizeof(HPDataType) * ph->capacity * 2);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ph->a = tmp;
ph->capacity = ph->capacity * 2;
}
//放入最后一个结点
ph->a[ph->size] = x;
ph->size++;
//进行向上调整
AdjustUp(ph->a, ph->size - 1);
}
向上调整
参数：存储堆数据的数组的地址、调整开始子结点位置下标
循环条件：子节点下标大于0
//参数：堆的地址、调整开始子结点
void AdjustUp(HPDataType* a, int child)
{
assert(a);
int parent = (child - 1) / 2;
while (child > 0)
{
//这里为大堆， 不满足大堆规则就交换
if (a[parent] < a[child])//大堆
//if (a[parent] > a[child])//小堆
{
Swap(&a[parent], &a[child]);
}
//满足就停止调整
else
{
break;
}
child = parent;
parent = (child - 1) / 2;
}
}
删除堆顶数据
- 先将堆顶和尾部数据交换
- 将尾部删除（有效位size–)
- 从新堆顶向下调整
void HeapPop(Heap* ph)
{
assert(ph);
assert(!HeapEmpty(ph));
//先将堆顶和堆尾交换
Swap(&ph->a[0], &ph->a[ph->size - 1]);
//将堆尾删除（有效位size--)
ph->size--;
//对新堆顶向下调整
AdjustDown(ph->a, ph->size, 0);
}
向下调整
参数：存储堆数据的数组的地址、向下调整的终点下标+1，开始调整的父结点下标
循环条件：子结点下标小于n
前提条件：堆顶和尾部数据交换再删除尾部数据后左右子树仍是堆
注意：判断右节点是否存在，即检查越界（当空间容量为偶数时，一定存在右结点，但不一定是有效空间，可能为随机值，所以并不能通过控制空间容量保证右结点的存在）
//参数：堆的地址、向下调整的终点，开始调整的父结点
void AdjustDown(HPDataType* a, int n, int parent)
{
assert(a);
//child为两子结点(若存在右子结点)中的较大值
int child = parent * 2 + 1;
while (child < n)
{
//if (child + 1 < n && a[child] < a[child + 1])//大堆
if (child + 1 < n && a[child] > a[child + 1])//小堆
{
child++;
}
//if (a[parent] < a[child])//大堆
if (a[parent] > a[child])//小堆
{
Swap(&a[parent], &a[child]);
}
else
{
break;
}
parent = child;
child = parent * 2 + 1;
}
}
3.推排序
先建堆，再调堆
对于无序数组{ 1, 345,12, 32, 56, 14, 2, 5, 10, 6 }
- 现在原数组上构建出堆，排升序建小堆，排降序建大堆，
- 建好堆再将堆顶与尾部数据交换，同时有效位减一，对交换后的堆顶进行向下调整，
- 若为排升序建小堆，第一次交换并调整后，尾部为最大值，堆顶为次大值，以此循环，完成排序
void HeapSort(int* a, int n)
{
// 堆排序中，升序需要构建大堆，这样最大值就会在堆顶
// 再将其与尾结点交换，size--，然后再进行向下调整，次大值来到堆顶， 如此往复
// 1.1向上调整构建堆（升序，大堆）
/*for (int i = 1; i < n; i++)
{
AdjustUp(a, i);
}*/
// 1.2向下调整构建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
// 2.交换堆顶堆尾，并向下调整（不包括调整后的尾结点）
while (n - 1 > 0)
{
Swap(&a[0], &a[n - 1]);
n--;
AdjustDown(a, n, 0);
}
return;
}
void TestHeapSort()
{
int a[10] = { 1, 345,12, 32, 56, 14, 2, 5, 10, 6 };
HeapSort(a, 10);
return;
}
堆排序时间复杂度
堆排序的时间复杂度为O(NlogN)*
但其两种建堆的时间复杂度是差别的
构建堆可通过向下调整建堆和向上调整建堆
- 向下调整建堆的时间复杂度为O(N)
- 向上调整建堆的时间复杂度为O(N*logN)
- 因为调堆的时间复杂度为O(NlogN)，所以两种建堆方法的堆排序的时间复杂度都为O(NlogN)
- 但是可以看出通过向下调整建堆效率更高
Topk问题
找出N个数中最大(最小)的前k个
- 当N比较小时，可以根据这N个数构建大堆(小堆)，再pop k次
- 当N很大时，在内存中构建N个数的堆就不适用了，借助文件操作完成堆排序。(若取最大的前k个)，此时将前k个数据构建小堆，再遍历剩下的数据，如果比堆顶大，则代替该堆顶进入堆，同时进行向下调整，最终此堆中即为最大的前k个
//打印出文件中最大的前k个数
void PrintTopk(const char* file, int k)
{
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen");
exit(-1);
}
int* topk = (int*)malloc(k * sizeof(int));
if (topk == NULL)
{
exit(-1);
}
//读取k个数到topk
for (int i = 0; i < k; i++)
{
int z = fscanf(fout, "%d", &topk[i]);
}
//在topk构建小堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(topk, k, i);
}
//继续读取文件数据，若大于堆顶，则入堆，并向下调整
int val = 0;
int ret = fscanf(fout, "%d", &val);
while (ret != EOF)
{
if (val > topk[0])
{
topk[0] = val;
AdjustDown(topk, k, 0);
}
ret = fscanf(fout, "%d", &val);
}
//此时topk中的是文件中最大的k个数
for (int j = 0; j < k; j++)
{
int e = topk[j];
printf("%d ", e);
}
printf("\n");
fclose(fout);
fout = NULL;
}
//创建并将测试数据写入文件
void CreatData()
{
srand((unsigned int)time(0));
FILE* fin = fopen("data.txt", "w");
if (fin == NULL)
{
perror("fopen");
exit(-1);
}
int n = 10000;
while (n--)
{
fprintf(fin, "%d ", rand() % 10000);
}
fprintf(fin, "%d ", 10000123);
fprintf(fin, "%d ", 1000089);
fprintf(fin, "%d ", 1000012222);
fprintf(fin, "%d ", 10000902);
//打印Topk，最大的k的数
fclose(fin);
fin = NULL;
}
void Test1()
{
CreatData();
PrintTopk("data.txt", 10);
}