蜜淘app在那个网站做的,大连哪家网站建设好,国外手机html5网站,罗湖商城网站设计制作一、什么是堆
在数据结构中#xff0c;堆#xff08;Heap#xff09;是一种特殊的树形数据结构#xff0c;用数组存储#xff0c;通常被用来实现优先队列。
堆具有以下特点#xff1a;
堆是一棵完全二叉树#xff08;Complete Binary Tree#xff09;#xff0c;即…
一、什么是堆
在数据结构中堆Heap是一种特殊的树形数据结构用数组存储通常被用来实现优先队列。
堆具有以下特点
堆是一棵完全二叉树Complete Binary Tree即除了最后一层外其他层都是满的且最后一层的节点从左到右排列。堆中的每个节点都满足堆的性质即父节点的值不小于或不大于其子节点的值这种性质被称为堆序性Heap Property。 最大堆Max Heap父节点的值不小于其子节点的值。最小堆Min Heap父节点的值不大于其子节点的值。堆中的根节点通常是位于最顶层的节点是堆中的最大或最小元素。在最大堆中根节点的值大于等于其子节点的值在最小堆中根节点的值小于等于其子节点的值。堆不保存节点之间的具体顺序只保证堆序性。堆可以用数组来表示根据节点的索引和父子节点的关系可以计算出节点之间的关系。
堆的常见操作有插入Insert、删除根节点Delete Max/Min和查找最大或最小元素。
堆的应用非常广泛常见的应用包括优先队列、堆排序、图算法如最短路径算法中的Dijkstra算法等。通过使用堆可以高效地在大量数据中插入、删除和获取最大或最小元素时间复杂度为O(log n)。 二、堆的实现
2.1 向上调整算法
2.1.1 思路
以大堆举例目的是要实现叶子节点要比所有的祖先节点小 考虑单次如果父节点比孩子结点小则二者交换考虑循环
循环体交换之后先前的父亲节点与孩子结点的下标值互换继续进行单次比较交换结束条件 一般的情况如果符合大堆的条件父节点大于子节点则可以跳出循环。 最坏的情况一直交换到了根节点如果在进行下去数组就会越界所以下标值应该0
2.1.2 代码
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 (child - 1) / 2;}else{break;}}
}
2.2 向下调整算法
2.2.1 思路
以小堆举例目的是要实现叶子节点要比所有的祖先节点大 考虑单次
先找到孩子节点中较小的结点如果父节点比孩子结点大则二者交换
考虑循环
循环体交换之后先前的父亲节点与孩子结点的下标值互换继续进行单次比较交换结束条件 一般的情况如果符合小堆的条件父节点小于子节点则可以跳出循环。 最坏的情况一直交换到了叶子节点如果在进行下去数组就会越界所以下标值应该n-1
2.2.2 代码
void AdjustDown(int* a, int n, int parent)
{//左孩子的下标int child parent * 2 1;while (childn){//找到两个孩子中较小的孩子-假设法if (child 1 n a[child 1] a[child]){child;}if (a[parent] a[child]){Swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}
}
2.3 插入
2.3.1 思路
从物理结构上讲插入到数组的最后一个位置然后用向上调整算法调整即可
2.3.2 代码
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);
}
2.4 删除
2.4.1 思路
删除一般删除的是堆顶的元素
如果直接删除然后用向下调整算法调整原来的子节点会变成父节点父节点会变成子节点。所以不可以采取此做法。
正确的做法将堆顶元素与堆底元素交换删除掉数组尾部元素向下调整原数组。这样就可以规避原堆父子关系全乱的问题
2.4.2 代码
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);
}
三、C语言源码汇总
3.1 heap.h
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.h//结构体定义
typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
//交换
void Swap(HPDataType* p1, HPDataType* p2);
//向上调整
void AdjustUp(HPDataType* a, int child);
//向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//初始化堆
void HPInit(HP* php);
//销毁堆
void HPDestroy(HP* php);
//插入
void HPPush(HP* php, HPDataType x);
//删除
void HPPop(HP* php);
//返回堆顶元素
HPDataType HPTop(HP* php);
//判断堆是否为空
bool HPEmpty(HP* php);
3.2 heap.c
#includeheap.hvoid HPInit(HP* php)
{assert(php);php-a NULL;php-size php-capacity 0;
}void HPDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 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 (parent 0)while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;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);
}void AdjustDown(HPDataType* a, int n, int parent)
{// 先假设左孩子小int child parent * 2 1;while (child n) // child n说明孩子不存在调整到叶子了{// 找出小的那个孩子if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}// logN
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;
}
四、堆的应用-TopK问题
4.1 分析
处理的是数据量非常大的情况下需要知道最大/最小的某几个数的问题。
由于建堆的空间复杂度是O(N)所以建堆的方式不可行需要直接在数组上操作。 正确的思路用前K个数建一个小堆剩下的数据跟堆顶数据比较如果比堆顶的数据大就替代堆顶进堆覆盖根位置然后向下调整 4.2 C语言源码
void CreateNDate()
{// 造数据int n 100000;srand(time(0));const char* file data.txt;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\n, x);}fclose(fin);
}void TopK()
{int k;printf(请输入k:);scanf(%d, k);int* heap (int*)malloc(sizeof(int) * k);if (heap NULL){perror(malloc fail);return;}const char* file data.txt;FILE* num fopen(file, r);if (num NULL){perror(fopen error);return;}// 读取文件中前k个数for (int i 0; i k; i){fscanf(num, %d, heap[i]);}// 建K个数的小堆for (int i (k - 1 - 1) / 2; i 0; i--){AdjustDown(heap, k, i);}// 读取剩下的N-K个数int x 0;while (fscanf(num, %d, x) 0){//更新小堆的数据并进行算法排序if (x heap[0]){heap[0] x;AdjustDown(heap, k, 0);}}printf(最大前%d个数: , k);for (int i 0; i k; i){printf(%d , heap[i]);}printf(\n);
}int main()
{CreateNDate();TopK();return 0;
}
文章转载自： http://www.morning.tgnwt.cn.gov.cn.tgnwt.cn http://www.morning.cpljq.cn.gov.cn.cpljq.cn http://www.morning.cnhgc.cn.gov.cn.cnhgc.cn http://www.morning.qdscb.cn.gov.cn.qdscb.cn http://www.morning.pphbn.cn.gov.cn.pphbn.cn http://www.morning.rwnx.cn.gov.cn.rwnx.cn http://www.morning.rqxtb.cn.gov.cn.rqxtb.cn http://www.morning.hqwtm.cn.gov.cn.hqwtm.cn http://www.morning.llqky.cn.gov.cn.llqky.cn http://www.morning.zbgqt.cn.gov.cn.zbgqt.cn http://www.morning.hyhqd.cn.gov.cn.hyhqd.cn http://www.morning.kjkml.cn.gov.cn.kjkml.cn http://www.morning.djpgc.cn.gov.cn.djpgc.cn http://www.morning.xqmd.cn.gov.cn.xqmd.cn http://www.morning.ywndg.cn.gov.cn.ywndg.cn http://www.morning.jczjf.cn.gov.cn.jczjf.cn http://www.morning.qrlsy.cn.gov.cn.qrlsy.cn http://www.morning.wkqrp.cn.gov.cn.wkqrp.cn http://www.morning.rzbgn.cn.gov.cn.rzbgn.cn http://www.morning.reababy.com.gov.cn.reababy.com http://www.morning.grbp.cn.gov.cn.grbp.cn http://www.morning.fwlch.cn.gov.cn.fwlch.cn http://www.morning.rwmft.cn.gov.cn.rwmft.cn http://www.morning.lnckq.cn.gov.cn.lnckq.cn http://www.morning.qxlxs.cn.gov.cn.qxlxs.cn http://www.morning.pbgnx.cn.gov.cn.pbgnx.cn http://www.morning.yppln.cn.gov.cn.yppln.cn http://www.morning.dmnqh.cn.gov.cn.dmnqh.cn http://www.morning.chtnr.cn.gov.cn.chtnr.cn http://www.morning.wzyfk.cn.gov.cn.wzyfk.cn http://www.morning.zbkwj.cn.gov.cn.zbkwj.cn http://www.morning.rwxnn.cn.gov.cn.rwxnn.cn http://www.morning.qsswb.cn.gov.cn.qsswb.cn http://www.morning.wrlff.cn.gov.cn.wrlff.cn http://www.morning.qfgxk.cn.gov.cn.qfgxk.cn http://www.morning.xhwty.cn.gov.cn.xhwty.cn http://www.morning.rnpnn.cn.gov.cn.rnpnn.cn http://www.morning.tdttz.cn.gov.cn.tdttz.cn http://www.morning.bbtn.cn.gov.cn.bbtn.cn http://www.morning.ngpdk.cn.gov.cn.ngpdk.cn http://www.morning.bchfp.cn.gov.cn.bchfp.cn http://www.morning.hwycs.cn.gov.cn.hwycs.cn http://www.morning.cffwm.cn.gov.cn.cffwm.cn http://www.morning.kkdbz.cn.gov.cn.kkdbz.cn http://www.morning.phxdc.cn.gov.cn.phxdc.cn http://www.morning.qzpw.cn.gov.cn.qzpw.cn http://www.morning.lrnfn.cn.gov.cn.lrnfn.cn http://www.morning.bnmrp.cn.gov.cn.bnmrp.cn http://www.morning.dnmgr.cn.gov.cn.dnmgr.cn http://www.morning.ryxdr.cn.gov.cn.ryxdr.cn http://www.morning.pwwdp.cn.gov.cn.pwwdp.cn http://www.morning.nkjpl.cn.gov.cn.nkjpl.cn http://www.morning.fbpdp.cn.gov.cn.fbpdp.cn http://www.morning.ctfh.cn.gov.cn.ctfh.cn http://www.morning.fndfn.cn.gov.cn.fndfn.cn http://www.morning.youyouling.cn.gov.cn.youyouling.cn http://www.morning.rjmb.cn.gov.cn.rjmb.cn http://www.morning.kjfqf.cn.gov.cn.kjfqf.cn http://www.morning.rjnm.cn.gov.cn.rjnm.cn http://www.morning.ltbwq.cn.gov.cn.ltbwq.cn http://www.morning.ljhnn.cn.gov.cn.ljhnn.cn http://www.morning.nwllb.cn.gov.cn.nwllb.cn http://www.morning.llcgz.cn.gov.cn.llcgz.cn http://www.morning.bksbx.cn.gov.cn.bksbx.cn http://www.morning.ngkgy.cn.gov.cn.ngkgy.cn http://www.morning.hgsmz.cn.gov.cn.hgsmz.cn http://www.morning.bbgr.cn.gov.cn.bbgr.cn http://www.morning.grjh.cn.gov.cn.grjh.cn http://www.morning.gqjwz.cn.gov.cn.gqjwz.cn http://www.morning.bfnbn.cn.gov.cn.bfnbn.cn http://www.morning.rkmhp.cn.gov.cn.rkmhp.cn http://www.morning.gyfhk.cn.gov.cn.gyfhk.cn http://www.morning.fhhry.cn.gov.cn.fhhry.cn http://www.morning.mhnxs.cn.gov.cn.mhnxs.cn http://www.morning.lrmts.cn.gov.cn.lrmts.cn http://www.morning.krrjb.cn.gov.cn.krrjb.cn http://www.morning.dpbgw.cn.gov.cn.dpbgw.cn http://www.morning.ysrtj.cn.gov.cn.ysrtj.cn http://www.morning.ytfr.cn.gov.cn.ytfr.cn http://www.morning.kqblk.cn.gov.cn.kqblk.cn
