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

【导读】华图事业单位考试网同步华图教育发布：2018年国家电网考试备考计算机之数据结构与算法(16)，详细信息请阅读下文！事业单位考试考情政策解读，点击领取备考资料，更多事业单位考试资讯请关注(htshiyedanwei)公众号，欢迎加入事业单位招聘考试交流群：  参加刷题、模考、领取备考资料，考编路上不孤单！

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

手机端链接：https://m.sydw.huatu.com/2017/1102/1601766.html

官方微信号

官方微博号