向上调整建堆

我们知道对一个数组建堆，有向下调整算法来建堆，但向上调整同样可以建堆。首先可以把数组中的第一个数据看成一个堆，第二个数据相当于插入第一个数据后面，再向上调整成一个堆。

向上调整算法与向下调整类似：

void AdjustUp(int* a, int child)
{int parent = (child - 1) / 2;while (child>0){if (a[child > a[parent]]){Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}

然后再进行建堆：

for (int i = 1;i < n;i++){AdjustUp(a, i);}

堆的代码实现

以大堆为例

Heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<stdbool.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void Swap(int* px, int* py);
void AdjustDown(int* a, int n, int parent);
void AdjustUp(int* a, int child);void HeapInit(HP* php, HPDataType* a, int n);
void HeapDestroy(HP* php);
//插入数据，并保持继续是堆
void HeapPush(HP* php, HPDataType x);
//删除堆顶数据，并保持之后继续是堆
void HeapPop(HP* php);
//获得堆顶数据，即最值
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);void HeapPrint(HP* php);

Heap.c

初始化堆

void HeapInit(HP* php, HPDataType* a, int n)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (php->a == NULL){printf("malloc fail\n");exit(-1);}memcpy(php->a, a, sizeof(HPDataType)*n);//建堆for (int i = (n - 1 - 1) / 2;i >= 0;i--){AdjustDown(php->a, n, i);}php->size = n;php->capacity = n;
}

销毁堆

void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = 0;php->capacity = 0;
}

插入数据

//插入数据，并保持继续是堆
void HeapPush(HP* php, HPDataType x)
{assert(php);//如果数组空间不够，扩容if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a, php->capacity * 2 * sizeof(HPDataType));if (php->a == NULL){printf("realloc fail\n");exit(-1);}}//插入数据php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

删除数据

//删除堆顶数据，并保持之后继续是堆
void HeapPop(HP* php)
{assert(php);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}

获取堆顶数据

//获得堆顶数据，即最值
HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php->a));return php->a[0];
}

判断堆是否为空

bool HeapEmpty(HP* php)
{assert(php);return php->size==0;
}

获取堆中数据个数

int HeapSize(HP* php)
{assert(php);return php->size;
}

打印堆中数据

void HeapPrint(HP* php)
{assert(php);for (int i = 0;i < php->size;i++){printf("%d ", php->a[i]);}printf("\n");
}

test.c

void TestHeap()
{int a[] = { 27, 37, 28, 18, 19, 34 };HP hp;HeapInit(&hp, a, sizeof(a) / sizeof(a[0]));HeapPrint(&hp);HeapPush(&hp,70);HeapPrint(&hp);HeapPop(&hp);HeapPrint(&hp);int k;scanf("%d", &k);//找出数组中最大的前k个while (!HeapEmpty(&hp) && k--){printf("%d ",HeapTop(&hp));HeapPop(&hp);}printf("\n");
}int main()
{TestHeap();return 0;
}

TOP-K问题

问题描述：在N个数中，找出最大/小的前K个数（一般情况下K远小于N）

• 解法1：使用堆排序。即建一个N个数的堆，不断选数，选出前K个。时间复杂度：O(N+K*log(N)).
• 解法2： 假设是找出最大的前K个数。用前K个数建一个小堆，剩下的数中逐个与堆顶的数相比，若比堆顶大就把数据换入堆中，再调整成堆。最后的这个小堆中的数就是最大的前K个数。这样解法更优了。

注意： 若要找最大的前K个数，是要建小堆而不是大堆。例如，如果有一个TOP-K的数还未进堆，那堆顶的数必然比这个数小，但不一定比堆中的其他数大，因为堆中的其他数可能存在有比这个数大的TOP-K的数，那这个TOP-K数就可以进堆了。如果是大堆，就不一定比堆顶数大，也就选不出最大的前K个数了。

代码实现（找出最小的前K个数）：

//选出最小的前K个数
void printTopK(int* a, int n, int k)
{HP hp;HeapInit(&hp,a,k);for (int i = k;i < n;i++){if (a[i] < HeapTop(&hp)){HeapPop(&hp);HeapPush(&hp, a[i]);}}HeapPrint(&hp);HeapDestroy(&hp);
}

测试：

void TestTopK()
{int n = 100000;int* a = (int*)malloc(sizeof(int) * n);srand(time(0));for (size_t i = 0; i < n; ++i){a[i] = rand() % 1000000;}a[5] = -1;a[1231] = -2;a[531] = -3;a[5121] = -4;a[115] = -5;a[2335] = -6;a[9999] = -7;a[76] = -8;a[423] = -9;a[3144] = -10;printTopK(a, n, 10);}int main()
{TestTopK();return 0;
}

结果：