堆的介绍~
堆的逻辑结构是一棵完全二叉树 堆的物理结构是一个数组
通过下标父子节点关系：leftchild=parent*2+1
rightchild=parent*2+2 parent=(child-1)/2
堆的两个特性
结构性
用数组表示的完全二叉树
有序性
任一节点的关键字是其他子树所有节点的最大值（或最小值）
最大堆：也称为大顶堆，最大值，所有父亲均大于孩子
最小堆：也称为小顶堆，最小值，所有父亲均小于孩子
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
void HPInit(HP* php);
void HPDestory(HP* php);
void HPPush(HP* php,HPDataType x);
void HPPop(HP* php);初始化
void HPInit(HP* php)
{
assert(php);
php->a=NULL;
php->capcacity=php->size=0;
}销毁
void HPDestory(HP* php)
{
assert(php);
free(php->a);
php->a=NULL;
php->capcacity=php->size=0;
}交换
void Swap(HPDataType* p1,HPDataType* p2)
{
HPDataType tmp=*p1;
*p1=*p2;
*p2=tmp;
}向上调整
void AdjustUp(HPDataType* a,int child)//建立小堆
{
int parent=(child-1)/2;
while(child>0) 实际上，结束条件是当child变为0（即到达根节点）或者当前节点不小于其父节点时
{
if(a[parent]>a[child]}
{
Swap(a[parent]>a[child]);
child=parent;//parent当上了child，继续向上调整
parent=(child-1)/2;
}
else
break;
}
}插入元素
void HPPush(HP* php,HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("realloc fail");
return;
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size]=x;
php->size++;
AdjustUp(php->a, php->size - 1);//传的是数组最后一个元素的下标 如果传size就越界了
}向下调整
void AdjustDown(HPDataType* a,int n,int parent)//参数 n 表示堆中当前有效元素的数量
{
int child=parent*2+1;//先假设左孩子小，并计算左孩子的索引
while(child<n)
//如果child大于n，说明孩子已经调整到n，调整到叶子结点了
// 如果子节点索引大于等于堆的大小，说明已经到达了叶子节点，无需继续调整
{
if(child+1<n&&a[child]<a[child+1])//首先要保证存在右孩子节点
{
++child;
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;//更新child为parent
child = parent * 2 + 1;
}
else
break;
}
}删除数据
void HPpop(HP* php)
{
assert(php);
assert(php->size>0);
Swap(&php->a[0], &php->a[php->size-1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}取栈顶数据
HPDataType HPTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}判空
bool HPEmpty(HP*php)
{
assert(php);
return php->size==0;
}test.c
方法一
void TestHeap1()
{
int a[] = { 4,2,8,1,5,6,9,7,3,2,23,55,232,66,222,33,7,1,66,3333,999 };
Hp hp;
HPInit(&hp);
for(size_t i=0;i<sizeof(a)/sizeof(int);i++)
{
HPPush(&hp,a[i]);
}
while(!HPEmpty(&hp))
{
printf("%d",HPTop(&hp);
}
HPDestory(&hp)；
}方法二
首先说明最后一个非叶子结点的坐标为什么是(n-1-1)/2?
- 堆的最后一个元素的索引是
n-1（因为数组是从0开始索引的）。 - 在完全二叉树中，如果一个节点的索引是
i，那么它的左子节点的索引是2*i+1，右子节点的索引是2*i+2 - 那么根据最后一个元素的索引是n-1，这个最后一个元素可以是左子节点，那么i=(n-1-1)/2,如果这个最后一个元素为右子节点，那么
void HeapSort(int* a,int n)
{
for(int i=(n-1-1)/2;i>0;i--)
{
AdjustDown(a, n, i);// 向下调整建堆 O(N)
}
// O(N*logN)
int end=n-1;
while(end>0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}
void TestHeap2()
{
int a[] = { 4,2,8,1,5,6,9,7,2,7,9};
HeapSort(a, sizeof(a) / sizeof(int));
}void CreatDate()
{
int n=100000;
srand(time(0));
const char* file="data.txt";
//fopen函数的返回值被存储在FILE类型的指针fin中
FILE* fin=fopen(file,"w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for(int i=0;i<n;i++)
{
int x = (rand()+i) % 10000000;
fprintf(fin,"%d",x);
}
fclose(fin);
}实现了一个基于堆（Heap）的数据结构来找出并输出给定文件data.txt中最大的前k个数
void TestHeap()
{
int k;
printf("请输入k：");
scanf("%d",&k);
int* kminheap=(int*)malloc(sizeof(int)*k);
if(kminheap==NULL)
{
perror("malloc fail");
return NULL;
}
const char*file="data.txt";
FILE* fout=fopen(file,"r");
if (fout == NULL)
{
perror("fopen error");
return;
}
for(int i=0;i<k;i++)
{
fscanf(fout,"%d",&kminheap[i]);
}
for (int i = (k-1-1)/2; i>=0 ; i--)
{
AdjustDown(kminheap, k, i);
}
int x=0;
while(fscanf(fout,%d,&x)>0)
{
if(kminheap[0]<x)
{
kminheap[0] = x;
AdjustDown(kminheap, k, 0);
}
}
printf("最大前%d个数：", k);
for (int i = 0; i < k; i++)
{
printf("%d ", kminheap[i]);
}
printf("\n");
}高度分析
满二叉树
最少情况
向下建堆计算
向上调整建堆
实践
假设有N个数，寻找最大的前k个（假设N远大于K）
方法1：
建立一个N个数的大堆 O（N）
Popk次 O（logN*k） popk次，每次调整一下时间复杂度是LogN . 就K*logN了
方法2：
用前k个数，建立一个小堆
剩下数据跟堆顶数据比较，如果比堆顶的数据大，就替代堆顶进堆(覆盖根位置，然后向下调整) O(logK*(N-K)) 这个小堆中的K个，就是最大的前K个
下面是先建K个数的小堆，再遍历剩下的数据，大的就交换到堆顶向下调整。就是logK(N-K)
关于为什么向上调整建立小堆，向下调整建立大堆？
向上调整与建立小堆（最小堆）
想象你有一堆球，这些球按照重量不同被分成了不同的层级，
最轻的球在最上面，最重的球在最下面（但实际上在堆中，我们是用数组来表示的，但这不影响我们的理解）。
现在，你想加入一个新的球到这个球堆中，但是你希望保持“最轻的球在最上面”的规则。
你把新球放在了球堆的最底部（因为没地方放了），但这时候你可能发现新球比它上面的某个球还要轻。
为了保持规则，你不得不把新球和它上面的那个球交换位置。如果交换后，新球还是比它新位置上面的球轻，你就继续交换，直到新球到了一个位置，它不再比上面的球轻了，或者它已经是最上面的球了。
这个过程就像新球在向上“爬”，所以我们称之为“向上调整”。通过这个过程，你确保了新加入的球不会破坏“最轻的球在最上面”的规则，也就是保持了最小堆的性质。
向下调整与建立大堆（最大堆）
现在，假设你有一堆球，但是这次是最重的球在最上面，最轻的球在最下面。这堆球是乱糟糟的，没有按照重量排好。你想要通过调整它们的位置，让最重的球总是在最上面，形成一个有序的“大堆”。
你从最下面开始，找出一个球（我们称它为“当前球”），然后看看它上面的两个球（如果有的话），哪个更重。
如果“当前球”比它上面的某个球还要重，那就把它们的位置交换一下，因为我们要让更重的球在上面。交换之后，“当前球”就上升了一个位置，变成了新的“上面”的球的一部分。然后，你对这个新的“上面”的球重复同样的过程，直到“当前球”不再需要交换位置了，或者它已经到了最上面。
这个过程就像是一个球在不断地向下“沉”，所以我们称之为“向下调整”。通过这个过程，你从底部开始，逐步地让整个球堆变得有序，最终形成了一个“最重的球在最上面”的大堆。
腾讯云开发者
