湛江住房和城乡建设部网站,浏览器怎么打开网站服务器连接,qq代刷网站推广,德国服务器网站文章目录一、堆的概念及结构二、堆的实现1.结构的定义2.堆的初始化3.堆的插入4.堆的向上调整5.堆的删除6.堆的向下调整7.取出堆顶元素8.返回堆的元素个数9.判断堆是否为空10.打印堆中的数据11.堆的销毁三、完整代码1.Heap.h2.Heap.c3.test.c四、堆排序1.堆排序2.建堆3.选数4.完…
文章目录一、堆的概念及结构二、堆的实现1.结构的定义2.堆的初始化3.堆的插入4.堆的向上调整5.堆的删除6.堆的向下调整7.取出堆顶元素8.返回堆的元素个数9.判断堆是否为空10.打印堆中的数据11.堆的销毁三、完整代码1.Heap.h2.Heap.c3.test.c四、堆排序1.堆排序2.建堆3.选数4.完整代码五、topK问题一、堆的概念及结构
如果有一个关键码的集合K {k0,k1,k2…kn-1}把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足Ki K 2*i1 且Ki K2*i2(Ki K2*i1 且 Ki K2*i2),i 0,1,2…则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆
堆的性质
堆中某个节点的值总是不大于或不小于其父节点的值
堆总是一棵完全二叉树
二、堆的实现
1.结构的定义
由于堆的元素是按完全二叉树的顺序存储方式存储在一个数组中所以堆的结构和顺序表的结构一样
ypedef int HPDataType; //数据类型重定义typedef struct Heap
{HPDataType* a; //指向动态开辟的数组int size; //记录数组元素是个数int capacity; //记录容量容量满时扩容
}HP;2.堆的初始化
堆的初始化和顺序表的初始化方式一样,我们可以先开辟一块空间也可以不开辟在插入数据的时候进行开辟我们这里先不开辟空间
//初始化堆
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size php-capacity 0;
}3.堆的插入
堆的插入我们需要注意两个地方
1.由于堆只会在数组的尾部插入数据所以我们不需要将CheckCapacity(检查容量)单独封装一个函数
2.由于我们在插入数据之后要保持堆的形态(大根堆或小根堆)所以我们需要对堆进行向上调整(调整数组里的数据使其保持堆的形态)向上调整的过程其实也是建堆的过程
//堆的插入 -- 插入x继续保持堆形态
void HeapPush(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);exit(-1);}php-a tmp;php-capacity newCapacity;}//插入元素php-a[php-size] x;php-size;//向上调整堆使其继续保持堆的形态AdjustUp(php-a, php-size - 1);
}
4.堆的向上调整
这里我们以小根堆为例如图假设现在我们已经有了一个小根堆现在我们在数组的最后(堆尾)插入一个数据那么就可能出现两种情况 1.插入的数据大于父亲节点此时我们的堆仍然保存小根堆的结构所以不需要进行调整比如我们在上面的堆中插入30 2.插入的数据小于父亲节点这时我们就需要进行向上调整直到根节点的大小小于父亲节点的大小(即小根堆)调整的次数由节点的大小决定可能调整1次也可能调整到根节点比如我们插入10 //交换两个节点
void Swap(HPDataType* p1, HPDataType* p2)
{assert(p1 p2);HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}
//堆的向上调整 --小根堆
void AdjustUp(HPDataType* a, int child)
{assert(a);int parent (child - 1) / 2; //找到父节点//while (parent 0) 当父亲为0时(0 - 1) / 2 0;又会进入循环while (child 0) //当调整到跟节点的时候不再继续调整{//当子节点小于父节点的时候交换if (a[child] a[parent]){Swap(a[child], a[parent]);//迭代child parent;parent (child - 1) / 2;}//否则直接跳出循环else{break;}}
}对于上面的代码我们需要注意循环结束的条件如果我们使用parent 0这个来判断结束时当父亲为0时(0 - 1) / 2 0;又会进入循环所以我们选择以孩子节点作为结束的条件child 0
【注意】如果我们需要建大根堆只需要把交换的条件修改一下即可
//当子节点小于父节点的时候交换
if (a[child] a[parent])5.堆的删除
对于堆的删除有明确的规定我们只能删除堆顶的元素但是顺序表头删又存在下面两个问题
1.顺序表头删需要挪动数据效率低下O(N)
2.头删之后堆中各节点的父子关系全被破坏了
对于上面的两个问题我们采用如下的解决方案
1.我们在删除之前先将堆顶的元素和堆尾的元素进行交换然后–size(删除数组的最后一个元素/堆尾元素)这个月就相当于删除了堆顶的元素并且时间复杂度从O(N)提升到了O(1)
2.由于我们把堆尾的元素交换到了堆顶堆的结构被破坏所以我们需要设计一个向下调整的算法来继续保持堆的形态
//删除堆顶元素 --找次大或者次小 -- logN
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));//首先交换堆顶和堆尾的元素Swap(php-a[0], php-a[php-size - 1]);//删除堆顶的元素php-size--;//向下调整保持堆的形态AdjustDown(php-a, php-size, 0);
}6.堆的向下调整
堆的向下调整和堆的向下调整刚好相反我们以小根堆为例我们调整的思路如下1.找出子节点中较小的节点
2.比较父节点和较小节点的大小如果父节点比子节点大就交换两个节点反之说明现在的形态已经是堆不需要进行调整了3.交换之后原来的子节点称为新的父节点然后继续执行1,2步骤直到调整为堆的结构 //堆的向下调整 --小根堆
void AdjustDown(HPDataType* a, int n, int parent)
{assert(a);int minchild parent * 2 1;while (minchild n){//找出那个较小的孩子if (a[minchild] a[minchild 1] minchild 1 n){minchild;}//当子节点小于父节点的时候交换if (a[minchild] a[parent]){Swap(a[minchild], a[parent]);//迭代parent minchild;minchild parent * 2 1;}else{break;}}
}和向上调整类似如果我们想要调整为大堆也只需要改变交换条件即可
// 找出较大的节点
if (a[maxchild] a[maxchild 1] axchild 1 n)
// 如果父节点小于子节点就交换
if (a[maxchild] a[parent])7.取出堆顶元素
堆顶元素就是数组的第一个元素
//获取堆顶的元素
HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php-a[0];
}8.返回堆的元素个数
/返回堆的元素个数
int HeapSize(HP* php)
{assert(php);return php-size;
}9.判断堆是否为空
//判断堆是否为空
bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}10.打印堆中的数据
//打印堆中的数据
void HeapPrint(HP* php)
{assert(php);for (int i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);
}11.堆的销毁
//堆的销毁
void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}三、完整代码
1.Heap.h
#pragma once //防止头文件被重复包含//包含头文件
#include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.htypedef int HPDataType; //数据类型重定义typedef struct Heap
{HPDataType* a; //指向动态开辟的数字int size; //记录数组元素是个数int capacity; //记录容量容量满时扩容
}HP;//初始化堆
void HeapInit(HP* php);
//堆的销毁
void HeapDestroy(HP* php);
//堆的插入
void HeapPush(HP* php, HPDataType x);
//堆的向上调整
void AdjustUp(HPDataType* a, int child);
//删除堆顶元素
void HeapPop(HP* php);
//堆的向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//获取堆顶的元素
HPDataType HeapTop(HP* php);
//判断堆是否为空
bool HeapEmpty(HP* php);
//返回堆的元素个数
int HeapSize(HP* php);
//打印堆中的数据
void HeapPrint(HP* php);2.Heap.c
#include Heap.h//初始化堆
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size php-capacity 0;
}//堆的销毁
void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}//堆的插入 -- 插入x继续保持堆形态
void HeapPush(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);exit(-1);}php-a tmp;php-capacity newCapacity;}//插入元素php-a[php-size] x;php-size;//向上调整堆使其继续保持堆的形态AdjustUp(php-a, php-size - 1);
}//交换两个节点
void Swap(HPDataType* p1, HPDataType* p2)
{assert(p1 p2);HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}//堆的向上调整 --小根堆
void AdjustUp(HPDataType* a, int child)
{assert(a);int parent (child - 1) / 2; //找到父节点//while (parent 0) 当父亲为0时(0 - 1) / 2 0;又会进入循环while (child 0) //当调整到跟节点的时候不再继续调整{//当子节点小于父节点的时候交换if (a[child] a[parent]){Swap(a[child], a[parent]);//迭代child parent;parent (child - 1) / 2;}//否则跳出循环else{break;}}
}
//删除堆顶元素 --找次大或者次小 -- logN
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));//首先交换堆顶和堆为的元素Swap(php-a[0], php-a[php-size - 1]);//删除堆顶的元素php-size--;//向下调整保持堆的形态AdjustDown(php-a, php-size, 0);
}//堆的向下调整 --小根堆
void AdjustDown(HPDataType* a, int n, int parent)
{assert(a);int minchild parent * 2 1;while (minchild n){//找出那个较小的孩子if (a[minchild] a[minchild 1] minchild 1 n){minchild;}//当子节点小于父节点的时候交换if (a[minchild] a[parent]){Swap(a[minchild], a[parent]);//迭代parent minchild;minchild parent * 2 1;}else{break;}}
}
//获取堆顶的元素
HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));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);
}3.test.c
#include Heap.hint main()
{int a[10] { 15, 18, 19, 25, 28, 34, 65, 49, 27, 37 };HP hp;//初始化堆HeapInit(hp);//建堆for (int i 0; i sizeof(a) / sizeof(a[0]); i){HeapPush(hp, a[i]);}//插入元素HeapPush(hp, 10);HeapPrint(hp);//删除堆顶元素HeapPop(hp);HeapPrint(hp);HeapPop(hp);HeapPrint(hp);//打印堆的元素while (!HeapEmpty(hp)){printf(%d , HeapTop(hp));HeapPop(hp);}printf(\n);return 0;
}【总结】
1.堆是二叉树顺序存储结构的一个具体体现堆中的每个节点的值总是不大于或不小于父节点的值(大堆/小堆)堆总是一棵完全二叉树堆使用顺序表进行存储
2.堆中父节点下标的计算公式(n-1)/2;左孩子下标n*21;右孩子下标n*22;
3.堆只能在尾部插入数据且插入数据后需要保证堆的结构所以在插入数据之后我们需要进行向上调整向上调整的时间复杂度为O(logN)(log以2为底)
4.堆只能在头部删除数据且删除数据后需要保证堆的结构又因为顺序表在头部删除数据需要挪动数据效率很低而且会破坏堆的结构所以在堆删除数据时会先将堆尾的数据和堆顶的数据进行交换然后–size(删除数组最后一个元素/队尾元素),再进行向下调整向下调整的时间复杂度为O(logN)(log以2为底)
四、堆排序
1.堆排序
堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。时间复杂度O(N*logN)空间复杂度O(1)
2.建堆
堆排序的第一步就是建堆建堆有两种方法向上调整建堆和向下调整建堆
**向下调整建堆**从最后一个非叶子节点(即最后一个叶子节点的父节点)开始向下调整直到调整到根节点 向下调整建堆的时间复杂度 调整次数 每一层节点个数 * 这一层节点最坏向下调整次数
T(N) 2^0*(h-1) 2^1*(h-2) 2^2*(h-3) 2^3*(h-4) …2^(h-2)*1
错位相减法
2*T(N) 2^1*(h-1) 2^2*(h-2) 2^3*(h-3) … 2^(h-2)*2 2^(h-1)*1
T(N) 2^0*(h-1) 2^1*(h-2) 2^2*(h-3) 2^3*(h-4) …2^(h-2)*1
两式相减得
T(N) -2^0*(h-1) 2^1 2^2 … 2^(h-2) 2^(h-1)
T(N) -h 2^0 2^1 2^2 … 2^(h-2) 2^(h-1)
T(N) -h 2^h-1
高度为h节点数量为N的完全二叉树,2^h-1N,h log(N1)(log以2为底)
T(N) N - log(N1)(log以2为底)
所以向下调整建堆的时间复杂度为O(N)
**向上调整建堆**把数组的第一个元素作为堆的根节点然后在堆尾一次插入其余元素每插入一个元素就向上调整一次从而保证堆的结构 **向上调整建堆的时间复杂度**由于堆的完全二叉树而满二叉树又是完全二叉树的一种所以此处为了简化计算使用满二叉树来计算时间复杂度(时间复杂度本身看来就是近似值多几个节点不影响最终结果) 我们知道调整次数 每一层节点个数 * 这一层节点最坏向下调整次数
T(N) 2^1*1 2^2*2 2^3*3 …2^(h-2)*(h-2) 2^(h-1)*(h-1)
精确算还是用错位相减法
高度为h节点数量为N的完全二叉树,2^h-1N,h log(N1)(log以2为底)
算大概就算最后一层2^(h-1)*(h-1)
2^(h-1)*(h-1) * 2/2
2^h*(h-1)/2
(N1)*(log(N1))/2
所以向上调整的时间复杂度为O(N*logN)
综合上面两种建堆的方式我们选择向下调整建堆所以建堆的时间复杂度为O(N);
3.选数
现在我们已经完成了建堆那么接下来就需要进行选数假设我们需要排升序那么方法一共有三种
1.建小堆开辟一个和原数组同等大小的新数组中每次取出堆顶元素(最小元素)放在新的数组中然后挪动数组中的数据最后排好序了以后再将新数组的数据覆盖到原数组
缺点每次挪动数据的效率很低且挪动数据会造成堆中的其余元素的父子关系混乱需要重新建堆而建堆的时间复杂度也是O(N)所以排N个数时间复杂度为O(N*N),空间复杂度为O(N)
2.建小堆我们借鉴Pop数据的方法先将堆顶的元素放在新的数组中然后交换堆顶和队尾的元素然后进行向下调数组的前n-1个数据直到排好序最后将新数组中的元素覆盖到原数组中
缺点虽然此方法可以让我们每次都拿到数组中最小的元素但是需要开辟额外的空间时间复杂度为O(N*lonN),空间复杂度为O(N)
3.建大堆先将堆顶和队尾的数据进行交换使得数组中最大的元素处于数组的末尾然后向下调整前n-1个元素使得次大的数据位于堆顶然后重复前面的步骤把次大的数据存放到最大的数据之前直到数组有序
优点没有额外的空间消耗且效率达到了O(N*logN)
综合上面的三种选数的方法选数的时间复杂度为O(N*logN),空间复杂度为O(N)
4.完整代码
#define _CRT_SECURE_NO_WARNINGS 1#include stdio.h
#include assert.h//空间复杂度O(1)
//时间复杂度O(N*logN)typedef int HPDataType;
//交换两个节点
void Swap(HPDataType* p1, HPDataType* p2)
{assert(p1 p2);HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}//堆的向上调整 --小根堆
void AdjustUp(HPDataType* a, int child)
{assert(a);int parent (child - 1) / 2; //找到父节点//while (parent 0) 当父亲为0时(0 - 1) / 2 0;又会进入循环while (child 0) //当调整到跟节点的时候不再继续调整{//当子节点小于父节点的时候交换//if (a[child] a[parent]) 大根堆if (a[child] a[parent]){Swap(a[child], a[parent]);//迭代child parent;parent (child - 1) / 2;}//否则跳出循环else{break;}}
}//堆的向下调整 --小根堆
void AdjustDown(HPDataType* a, int n, int parent)
{assert(a);int minchild parent * 2 1;while (minchild n){//找出那个较小的孩子if (a[minchild] a[minchild 1] minchild 1 n){minchild;}//if (a[minchild] a[parent]) 大根堆//当子节点小于父节点的时候交换if (a[minchild] a[parent]){Swap(a[minchild], a[parent]);//迭代parent minchild;minchild parent * 2 1;}else{break;}}
}
void HeapSort(int* a, int n)
{/* 建堆 -- 向上调整建堆 - O(N*logN)for (int i 1; i n; i){AdjustUp(a, i);}*/// 大思路选择排序依次选数从后往前排// 升序 -- 大堆// 降序 -- 小堆//建堆 -- 向下调整建堆 - O(N)for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDown(a, n, i);}int i 1;while (i n){Swap(a[0], a[n - i]); // 交换堆尾和堆顶的数据AdjustDown(a, n - i, 0); //向下调整i;}
}int main()
{int a[] { 15, 1, 19, 25, 8, 34, 65, 4, 27, 7 };HeapSort(a, sizeof(a) / sizeof(int));for (int i 0; i sizeof(a) / sizeof(int); i){printf(%d , a[i]);}printf(\n);return 0;
}五、topK问题
TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大,比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。
N个数找前K个最大的如何处理
1.排序 --O(N*logN)
2.堆选数
(1)建大堆建N个数的大堆选K次即可(Pop K次) O(N)O(N*logK)
(2)建小堆假设N很大K很小比如N100亿K100那么(1)方法就不行了
N很大的时候内存就存不下了就只能存在磁盘中
100亿整数40G
400亿Byte
1G1024MB
1024MB1024*1024KB
1024*1024KB1024*1024*1024Byte
时间复杂度为O(K)O(logK*(N-K)) 空间复杂度 O(K)
思路前K个数建K个数的小堆依次遍历后续N-K个数比堆顶的数据大就替换堆顶数据向下调整建堆
最佳的方式就是用堆来解决基本思路如下
第一步用数据集合中的前K个元素来建堆–前K个最大元素则建小堆前K个最小元素则建大堆
第二步用剩余的N-K个元素依次与堆顶的元素进行比较前K大的元素则大于堆顶元素则就替换堆顶数据进行向下调整前K小的元素则小于堆顶的元素替换堆顶数据进行向下调整
#include stdio.h
#include stdlib.h// 交换两个节点
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}// 向下调整 --建小堆
void AdjustDown(int a[], int n, int parent)
{int minchild parent * 2 1; // 找到左孩子(左孩子 1得到右孩子)while (minchild n) // 调整到数组尾时不在调整{if (minchild 1 n a[minchild 1] a[minchild]){minchild 1;}if (a[parent] a[minchild]){Swap(a[parent], a[minchild]);}else{break;}}// 迭代parent minchild;minchild parent * 2 1;
}int* TopK(int* a, int n, int k)
{// 开辟K个元素的空间int* minHeap (int*)malloc(sizeof(int) * k);if (minHeap NULL){perror(malloc fail);return NULL;}// 将数组的前K个元素for (int i 0; i k; i){minHeap[i] a[i];}// 建小堆 --向下调整建堆O(N)// n-1找到最后一个叶子节点该节点-1/2找到倒数第一个父节点for (int i (k - 1 - 1) / 2; i 0; i--){AdjustDown(minHeap, k, i);}// 取N-K个元素与堆顶元素比较如果大于堆顶元素就如堆for (int i k; i n; i){if (minHeap[0] a[i]){minHeap[0] a[i];AdjustDown(minHeap, k, 0);}}return minHeap;
}int main()
{int arr[] { 15,1,19,25,8,34,65,4,27,7 };int n sizeof(arr) / sizeof(arr[0]);// TopK问题--前K个最大的元素int k 3;int* ret TopK(arr, n, k);for (int i 0; i k; i){printf(%d , ret[i]);}free(ret);ret NULL;return 0;
}
c;minchild parent * 2 1;
}int* TopK(int* a, int n, int k)
{// 开辟K个元素的空间int* minHeap (int*)malloc(sizeof(int) * k);if (minHeap NULL){perror(malloc fail);return NULL;}// 将数组的前K个元素for (int i 0; i k; i){minHeap[i] a[i];}// 建小堆 --向下调整建堆O(N)// n-1找到最后一个叶子节点该节点-1/2找到倒数第一个父节点for (int i (k - 1 - 1) / 2; i 0; i--){AdjustDown(minHeap, k, i);}// 取N-K个元素与堆顶元素比较如果大于堆顶元素就如堆for (int i k; i n; i){if (minHeap[0] a[i]){minHeap[0] a[i];AdjustDown(minHeap, k, 0);}}return minHeap;
}int main()
{int arr[] { 15,1,19,25,8,34,65,4,27,7 };int n sizeof(arr) / sizeof(arr[0]);// TopK问题--前K个最大的元素int k 3;int* ret TopK(arr, n, k);for (int i 0; i k; i){printf(%d , ret[i]);}free(ret);ret NULL;return 0;
}
