《算法导论》笔记 第6章 6.1堆

【笔记】

堆被定义为一棵完全二叉树，在数据结构中通常采用数组形式实现这种树形结构。其中根元素被存储在数组A的第一个位置上，在该结构中对于任意一个索引值i来说：其父节点的位置等于i除以2向下取整；左子节点的位置等于i乘以2；右子节点的位置则等于i乘以2加1。

该二叉树数据结构包含两类主要实现形式：最大优先队列与最小优先队列（亦即大根堆与小根堆）。其中对于任意节点i而言，在大根堆中其父节点位置满足A[PARENT(i)] >= A[i]这一条件，并且最大的元素位于树根位置。

一个结点在根节点处的高度定义为其到叶子节点的最长下降路径中的边的数量。堆的最大深度等于树根节点的最大深度。

【练习】

6.1-1 在高度为h的堆中，最多和最少的元素个数是多少？

最多：

最少：

6.1-2 证明：含n个元素的堆的高度为 logn

6.1-3 证明：在一个最大堆的某棵子树中，最大元素在该子树的根上。

假设存在一棵子树T'⊆T，在T'中其最大元素不在根节点上，则该最大元素的编号为m，并满足A[m] ≥ A[PARENT(m)]。

∵ 在最大堆上，A[ PARENT(i) ] >= A[ i ]

∴ A[ PARENT(m) ] >= A[ m ]

与假设矛盾，因此在一个最大堆的某棵子树中，最大元素在该子树的根上。

在给定的最大堆中（其中所有元素互不相同），该最小值可能位于何处。

当只有一个元素时，最小元素可能在根节点。

否则，最小元素只能在叶子结点上

由反正法，假设有最小元素不在叶子结点上，则其存在子结点 i。

∵ 所有元素都不相同，A[ PARENT(i) ] >= A[ i ]

∴ A[ PARENT(i) ] > A[ i ]

又∵ PARENT(i) 是最小的元素

∴ A[ PARENT(i) ] < A[ i ]

与假设矛盾，因此最小元素只能在叶子结点上。

6.1-5 一个已排好序的数组是一个最小堆吗？

给定数组 A 已按升序排列， 则 A[ i ] <= A[ j ] (i<j)

假设 i 为 A 中任意一元素，则A[ i/2 ]是 i 的父结点。

由于 A[ i ] <= A[ j ] (i<j)，则 A[ i/2 ] <= A[ i ]

满足最小堆的性质 A[ PARENT(i) ] <= A[ i ]，因此已排好序的数组是一个最小堆。

6.1-6 序列 <23,17,14,6,13,10,1,5,7,12> 是一个最大堆吗？

A[4] = 6 , A[RIGHT(4) = 9] = 7 。与最大堆的性质矛盾。

不是最大堆。

6.1-7 证明：当用数组表示存储了n个元素的堆时，叶子结点的下标是n/2+1,n/2+2....n。

当i等于n的一半时，
如果n是偶数，
左边函数值即为n，
此时i只有一个子节点；
反之，
如果n是奇数，
右边函数值即为n，
此时i有两个子节点。

当下标 i > n/2 时，LEFT(i)、RIGHT(i) 皆大于n，因此 i 没有子结点，i 是叶子结点。