目录

一、堆的实现

1.1堆数据的插入

1.2堆数据的删除

二、建堆算法

2.1向上调整建堆

2.2向下调整建堆

三、堆的应用

3.1堆排序

3.2Top—K问题

一、堆的实现

1.1堆数据的插入

插入一个数据后不再是小堆需要将新数据调整到合适的位置，所以堆的插入就是在数组插入数据再向上调整即可

堆数据的插入

1.检查空间是否需要扩容

2.赋值size++

3.向上调整

<code>void AdjustUp(HPDataType* a,int size)

{

int child = size - 1;

while (child > 0)

{

int parent = (child - 1) / 2;//父亲结点

if (a[child] < a[parent])//判断 小于建小堆

{

Swap(&a[child], &a[parent]);

child = parent;

}

else

{

break;

}

}

}

void HPPush(HP* php, HPDataType x)

{

assert(php);

if (php->capacity == php->size)

{

int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;

HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType)*newcapacity);//这是 php->a的动态内存

if (tmp == NULL)

{

perror("fail realloc");

return;

}

php->a = tmp;

php->capacity = newcapacity;

}

php->a[php->size++] = x;

AdjustUp(php->a, php->size);

}

1.2堆数据的删除

分析：

因此：

代码：

<code>void AdjustDown(HPDataType* a, int size, int parent)

{

int child = 2 * parent + 1;

while (child<size)//结束条件不能越界

{

//假设法求出最小的孩子

if (child + 1 < size && a[child] > a[child + 1])

{

child = child + 1;

}

//调整

if (a[parent] > a[child])

{

Swap(&a[parent], &a[child]);

//更新父亲孩子结点

parent = child;

child = 2 * parent + 1;

}

else

{

break;

}

}

}

void HPPop(HP* php)//删除根结点

{

assert(php && php->size > 0);

Swap(&php->a[0], &php->a[php->size - 1]);

php->size--;

AdjustDown(php->a, php->size, 0);

}

二、建堆算法

2.1向上调整建堆

堆插入的过程其实就是建堆，在一个堆的末尾插入数据然后向上调整形成一个新的堆

<code>void AdjustUp(HPDataType* a, int size)

{

int child = size - 1;

while (child > 0)

{

int parent = (child - 1) / 2;//父亲结点

if (a[child] > a[parent])//判断 小于建小堆

{

Swap(&a[child], &a[parent]);

child = parent;

}

else

{

break;

}

}

}

向上调整建堆时间复杂度分析

根据大O渐进法，向上调整建堆的时间复杂度即 O(N*logN）

2.2向下调整建堆

从最后一个父亲结点开始依次向下调整

根据大O渐进法，向下调整建堆的时间复杂度即 O(N）

对比向上调整建堆，h-1层向下调整只需要移动1层，而向上调整需要移动h-1次因此向下调整是更优的建堆算法

三、堆的应用

3.1堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆

升序：建大堆

降序：建小堆

2. 利用堆删除思想来进行排序 

演示代码：

<code>//升序向下调整

void SAdjustDown(HPDataType* a, int size, int parent)

{

int child = 2 * parent + 1;

while (child < size)//结束条件不能越界

{

//假设法求出最小的孩子

if (child + 1 < size && a[child] < a[child + 1])

{

child = child + 1;

}

//调整

if (a[parent] < a[child])

{

Swap(&a[parent], &a[child]);

//更新父亲孩子结点

parent = child;

child = 2 * parent + 1;

}

else

{

break;

}

}

}

void HeapSort(int* a, int n)

{

//升序建大堆

//降序建小堆

向上建堆

//for (int i = 1; i < n; i++)

//{

////相当于慢慢插入数据建堆

//SAdjustUp(a, i);

//}

//向下调整建堆

for (int i = (n - 1 - 1) / 2; i >= 0; i--)

{

SAdjustDown(a, n, i);

}

int end = n - 1;

while (end > 0)

{

Swap(&a[0], &a[end]);

SAdjustDown(a, end, 0);

end--;

}

}

 堆排序的时间复杂度：

对比向上调整建堆

可以知道堆排序时间复杂度：O（N*logN）

3.2Top—K问题

Top—K问题：N个数中求最大的（最小的）前K个数据，一般N远大于K

实例：专业前5名、富豪榜、游戏战力榜等等

方法一：

建一个N个数的大堆  O（N）

Pop k次数据         O（N*logN）

此方法缺陷也很明显如果N太大，排序就不太可取，甚至数据都无法一下子加载到内存中

方法二：

用前K个数建一个小堆   O（K）

剩下数据与堆顶数据比较，如果比堆顶数据大，那么替代堆顶进堆（覆盖堆顶数据然后向下调整）

O（logK*（N-K）（最坏情况都需要覆盖调整）

复杂度：O（N）

分析：

剩下的N-K个数据依次与堆顶数据比较

<1>数据比堆顶数据小，那么不可能为最大的前K个

<2>数据比堆顶数据大，覆盖调整之后形成一个新的小堆，再次比较

比较完所有的数后那么小堆中就是最大的前K个数据

代码实现

先生成十万个数据

<code>void CreatData()

{

int n = 100000;//生成10万个数据

srand(time(0));//生成不同的种子

FILE* file = fopen("qsy.txt", "w");//打开文件

for (int i = 0; i < n; i++)

{

int x = rand() % 100001 + i;//生成随机数

fprintf(file, "%d\n", x);//写数据

}

fclose(file);//关闭文件

file = NULL;

}

开K个空间从 qsy 文件里读取数据建堆

之后再读取数据比较堆顶数据覆盖调整

<code>void CreatData()

{

int n = 100000;//生成10万个数据

srand(time(0));//生成不同的种子

FILE* file = fopen("qsy.txt", "w");//打开文件

for (int i = 0; i < n; i++)

{

int x = rand() % 100001 + i;//生成随机数

fprintf(file, "%d\n", x);//写数据

}

fclose(file);//关闭文件

file = NULL;

}

int main()

{

CreatData();

int k;

scanf("%d", &k);

int* kmin = (int*)malloc(10 * sizeof(int));

if (kmin == NULL)

{

perror("malloc fail");

return 1;

}

//读取数据

FILE* pf = fopen("qsy.txt", "r");

for (int i = 0; i < k; i++)

{

fscanf(pf, "%d", &kmin[i]);

}

//建k个数的小堆

for (int i = (k - 1 - 1) / 2; i >= 0; i--)

{

JAdjustDown(kmin, k, i);

}

//比较数据

int x;

while (fscanf(pf, "%d", &x) != EOF)

{

if (x > kmin[0])

{

kmin[0] = x;

JAdjustDown(kmin, k, 0);

}

}

//打印数据

for (int i = 0; i < k; i++)

{

printf("%d ", kmin[i]);

}

return 0;

}