北京事业单位考试

您当前位置:公务员考试网 > 北京人事考试网 > 北京事业单位考试 > 备考资料 > 2018国家电网考试备考计算机之数据结构与算法(12)

2018国家电网考试备考计算机之数据结构与算法(12)

2018-03-09 14:18:49 事业单位考试网 http://bj.huatu.com/sydw/ 文章来源:北京华图

  【导读】华图事业单位考试网同步北京华图发布:2018国家电网考试备考计算机之数据结构与算法(12)--详细信息请阅读下文!更多资讯请关注北京华图微信公众号(bjhuatu),事业单位培训咨询电话:400-010-1568

  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).

(编辑:刘冉)
北京华图:bjhuatu
想考上公务员的人都关注了我们!
立即关注

10万+
阅读量
10w+
粉丝
10000+
点赞数

联系我们
微信二维码

北京华图教育官方微信

北京华图

北京市海淀区花园路7号新时代一层

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

客服热线:400-010-1568

网站:http://bj.huatu.com

  • 牡丹园校区
  • 西城校区
  • 朝阳校区
  • 顺义校区
  • 大兴校区
  • 昌平校区
  • 平谷校区
  • 房山校区

海淀区花园路7号新时代大厦一层

客服热线:400-010-1568

网站:http://bj.huatu.com

西城区阜成门万通新世界A座1211

客服热线:010-58463857

网站:http://bj.huatu.com

朝阳区定福庄北里一号院鲁班大厦809室

客服热线:010-59453600/57237009

网站:http://bj.huatu.com

顺义双兴北区10号楼底商(北城根路与光明北街交叉路口)

客服热线:010-57282681

网站:http://bj.huatu.com

大兴区金星西路绿地中央广场B座609室

客服热线:010-58463856

网站:http://bj.huatu.com

昌平区政府街4-3号特步专卖店二楼(昌平二中斜对面)

客服热线:010-57282680

网站:http://bj.huatu.com

平谷区建设街229号二层(平谷六中北路口往西50米)

客服热线:010-59146957

网站:http://bj.huatu.com

房山区良乡拱辰南大街荣鹏花园底商

客服热线:010-57428000

网站:http://bj.huatu.com