0591-87896332
微信
微信 福建华图
微信号:fjhuatu
+ 关注
QQ

福建分校

您当前位置:福建人事考试网 > 福建事业单位考试 > 备考技巧 > 专业课 > 2016秋季龙岩市武平县事业单位考试:计算机之数据结

2016秋季龙岩市武平县事业单位考试:计算机之数据结构与算法之图的遍(3)

2016-07-07 22:46:06 福建事业单位考试文章来源:福建省公务员考试网公众号QQ群华图在线APP

 【导读】2016秋季龙岩市武平县事业单位考试:计算机之数据结构与算法之图的遍历福建事业单位微信公众号(fjsyzk),福建事业单位培训咨询电话:0591-87896332,微信咨询请扫描下方二维码:

2024年福建公务员时政一锅端

 7.堆 (Heap)

  在计算机科学中,堆是一种特殊的树形数据结构,每个结点都有一个值。通常我们所说的堆的数据结构,是指二叉堆。堆的特点是根结点的值小(或大),且根结点的两个子树也是一个堆。

  例程

  为将元素X插入堆中,找到空闲位置,建立一个空穴,若满足堆序性(英文:heap order),则插入完成;否则将父节点元素装入空穴,删除该父节点元素,完成空穴上移。直至满足堆序性。这种策略叫做上滤(percolate up)。

  void Insert( ElementType X, PriorityQueue H ){ int i; if( IsFull(H) ) { printf( "Queue is full.\n" ); return; } for( i = ++H->Size; H->Element[i/2] > X; i /= 2 ) H->Elements[i] = H->Elements[i/2]; H->Elements[i] = X;}

  以上是插入到一个二叉堆的过程。

  DeleteMin,删除小元,即二叉树的根或父节点。删除该节点元素后,队列后一个元素必须移动到堆得某个位置,使得堆仍然满足堆序性质。这种向下替换元素的过程叫作下滤。

  ElementType DeleteMin( PriorityQueue H ){ int i, Child; ElementType MinElement, LastElement; if( IsEmpty( H ) ) { printf( "Queue is empty.\n" ); return H->Elements[0]; } MinElement = H->Elements[1]; LastElement = H->Elements[H->Size--]; for( i = 1; i*2 <= H->Size; i = Child ) { /* Find smaller child. */ Child = i*2; if( Child != H->Size && H->Elements[Child+1] < H->Elements[Child] ) Child++; /* Percolate one level. */ if( LastElement > H->Elements[Child] ) H->Elements[i] = H->Elements[Child]; else break; } H->Elements[i] = LastElement; return MinElement;}

  7.算法设计的分析技术

  算法是对问题求解过程的准确描述,由有限条指令组成,这些指令能在有限时间内执行完毕并产生确定性的输出。

  进行算法的时间复杂度分析,就是求其T(n),并用O、Ω或是Θ以尽可能简单的形式进行表示。

  理想情况下,希望能够使用Θ表示算法的时间复杂性。退而求其次,可以使用O或是Ω。

  使用O时,希望估计的上界的阶越小越好。

  使用Ω时,希望估计的下界的阶越大越好。

  树的高度为ëlognû,所以将一个元素插入大小为n的堆所需要的时间是O(logn).

  delete(H,i) 所需要的时间是O(logn).

  make-heap(A): 从数组A创建堆

  方法1:从一个空堆开始,逐步插入A中的每个元素,直到A中所有元素都被转移到堆中。

  时间复杂度为O(nlogn).

  方法2:

  MAKEHEAP(创建堆)

  输入:数组A[1…n]

  输出:将A[1…n]转换成堆

  1. fori← ën/2û downto 1

  2. Sift-down(A,i){使以A[i]为根节点的子树调整成为堆,故调用down过程}

  3. endfor

  时间复杂度为O(n).

  ——推荐阅读——

  招聘公告--2024年福建事业单位招聘考试日历 | 职位表查询

  考试报名--2024年福建事业单位招聘报名入口 | 报名问题咨询

  备考指导--历年福建事业单位进面分数线 | 每日刷题练习 | 模考练习

  课程推荐--2024年福建事业单位图书教材 | 网课推荐 | 面授课程

(编辑:admin)
有疑惑?在线客服帮你

公告什么时候出?

报考条件是否符合?

公考小白怎么备考?

冲刺资料怎么领取?

立即咨询
福建华图:fjsyzk
想考上事业单位的人都关注了我们!
立即关注

700w+
阅读量
100w+
粉丝
300w+
点赞数

联系我们
微信二维码

福建华图微信

华图总部:北京华图宏阳教育文化发展股份有限公司

联系电话:010-68296100

联系地址:北京市海淀区复兴路甲23号

福建华图总部

福州市鼓楼区五四路82号融都国际大厦9层 热线:0591-87896332

网站:https://fj.huatu.com

  • 福州华图
  •  大学城 
  • 福清华图
  • 长乐华图
  • 宁德华图
  • 福鼎华图
  • 福安华图
  • 莆田华图
  • 仙游华图
  • 三明华图
  • 永安华图
  • 大田华图
  • 宁化华图
  • 南平华图
  • 建阳华图
  • 松溪华图
  • 厦门华图
  • 湖里华图
  • 集美华图
  • 同安华图
  • 泉州华图
  • 晋江华图
  • 德化华图
  • 安溪华图
  • 漳州华图
  • 漳浦华图
  • 龙海华图
  • 平和华图
  • 诏安华图
  • 长泰华图
  • 龙岩华图
  • 上杭华图
  • 华图总部

福州市鼓楼区五四路82号融都国际大厦9层

客服热线:0591-87896332

网站:https://fuzhou.huatu.com

闽侯县上街余盛91号院子
(福州大学城博士后购物广场往洪塘大桥100米处-木水五金店旁巷子进去15米)

客服热线:0591-87618197

网站:https://fuzhou.huatu.com

福清市清昌大道万达广场A1座23A09华图教育

客服热线:0591-85153698

网站:https://fuzhou.huatu.com

福州市长乐区(福州外语外贸学院旁)美食街A栋4楼

客服热线:0591-87896332

网站:https://fuzhou.huatu.com

福建省宁德市蕉城区蕉城南路94号泓源国际9楼

客服热线:0593-2837612

网站:https://ningde.huatu.com

福建省宁德福鼎市太姥大道80号2楼(惠通五金楼上宏利小区10-1)华图教育

客服热线:0593-7860132

网站:https://ningde.huatu.com

已关闭学习中心,咨询课程请联系市区招生老师

客服热线:0593-2837612

网站:https://ningde.huatu.com

莆田市城厢区荔城南大道正容大厦8楼华图教育

客服热线:0594-2660266

网站:https://putian.huatu.com

仙游县香港财富中心1期学府40号 华图教育

客服热线:0594-8661179

网站:https://putian.huatu.com

三明市梅园国际大酒店27楼

客服热线:0598-8912978

网站:https://sanming.huatu.com

已关闭学习中心,咨询课程请联系市区招生老师

客服热线:0598-8912978

网站:https://sanming.huatu.com

三明大田均溪镇赤岩山路34号3楼

客服热线:18020832295

网站:https://sanming.huatu.com

三明市宁化县中环中路127号新华书店4楼华图教育

客服热线:18054951439

网站:https://sanming.huatu.com

南平市延平区八一路320号外贸大厦4楼华图教育

客服热线:0599-8827506

网站:https://nanping.huatu.com

南平市建阳区中山广场C座203(步行街)

客服热线:0599-5636383

网站:https://nanping.huatu.com

松溪县红旗街222号5楼(妇幼保健院斜对面)

客服热线:15505908145

网站:https://nanping.huatu.com

厦门市思明区鹭江道100号财富中心大厦三楼

客服热线:0592-5168870

网站:https://xiamen.huatu.com

厦门市湖里区湖里大道41号联泰大厦4楼408

客服热线:18050118013

网站:https://xiamen.huatu.com

厦门市集美区岑西路124号 886兑换商城2层

客服热线:0592-6155164 6157525

网站:https://xiamen.huatu.com

厦门市同安区城南路大唐世家一期217号(钟楼旁边2楼)

客服热线:0592-5887383

网站:https://xiamen.huatu.com

泉州丰泽区泉秀路领SHOW天地东区创意办公D栋3层

客服热线:0595-22025188

网站:https://quanzhou.huatu.com

晋江市泉安中路国贸中心大厦5楼518

客服热线:0595-82027170

网站:https://quanzhou.huatu.com

德化县龙湖街龙湖大厦2楼华图教育(龙湖车站河对面)

客服热线:15359970270

网站:https://quanzhou.huatu.com

泉州市安溪县河滨北路茶博汇五期4-116商城(外滩不夜城)

客服热线:15394434045

网站:https://quanzhou.huatu.com

漳州市龙文区客运中心4号

客服热线:0596-2899579

网站:https://zhangzhou.huatu.com

漳州市漳浦县永嘉天地商业别墅6号(永嘉国美电器斜对面)

客服热线:0596-3899579

网站:https://zhangzhou.huatu.com

漳州市龙海市石码镇解放北路红树林冬藏阁7栋302室

客服热线:0596-6606360

网站:https://zhangzhou.huatu.com

漳州市平和县正兴大道正兴大道46号(交通大厦对面)

客服热线:18960060521

网站:https://zhangzhou.huatu.com

诏安县南诏镇梅中西路221号(良峰公园旁)

客服热线:18059625702

网站:https://zhangzhou.huatu.com

漳州市长泰县万豪天悦广场2楼

客服热线:17365163789

网站:https://zhangzhou.huatu.com

龙岩市新罗区登高西路香樟名都(苹果专卖店楼上)

客服热线:0597-2811883

网站:https://longyan.huatu.com

龙岩市上杭县帝豪大酒店19楼1916

客服热线:0597-3859967

网站:https://longyan.huatu.com

总部地址

地址:北京市海淀区复兴路甲23号

邮编:100036

行政总机:4006-01-9999

全国热线热线:4006-01-9999