分类： C/C++
2016-09-23 15:24:29
堆（二叉堆）数据结构是一中数组对象，它可以被视为一棵完全二叉树。
为方便起见。我们的分析基于 堆的第一个元素为A[1] ,并且堆的元素都是正整数。
这里我们分析最大堆。
堆的结构性质：
容易证明一棵高位 h二叉树的节点个数n 满足 2^h<=n<=2^(h+1)-1;由这个公式我们不难得到 h= lgN(向下取整)。对于数组中任意位置i上的元素，其左儿子在位置2i上，右 儿子在位置（2i+1）上，它的父亲节点则在i/2（向下取整）上。
我们定义 LEFT(i)=2*I RIGHT(i)=2*i+1; PARENT(i)=i/2(向下取整) （这里你可以用移位操作使操作跟快）
这种利用数组存储，并且也没有用到指针的结构在大部分计算机上运行很可能非常快，不过一个需要考虑的问题是，堆的大小需要事先估计(当然你可以使用动态分配内存 的技术，来分配一个暂时需要的大小，但你依旧要考虑当元素快要存满数组时，需要有及时调整数组大小的机制)。因此，我们下面的分析基于这样一个堆数据结构，它由 一个数组（当然它可以是任意类型）一个代表 堆允许的最大大小的整数和一个代表当前大小的整数。
这里我们给出它的定义：
Structheap
{
Int *array;
Int MAXSIZE;
Int current_sizee;
}
Typedefstruct heap*Heap
堆的堆序性质：
我们想要快速的得到最大元，因此最大元应该在根上（即a[1]上）如果我们考虑任意子树也应该是一个堆，那么任意节点就应该大于它的儿子节点。
这样，我们便得到堆的堆序性质：在一个堆中，任意节点x，x的父节点的关键字不小于x的关键字（根节点除外），x的儿子节点关键字不大于x节点的关键字。
依赖于堆序我们可以在常数时间内取得一组元素中的最大值。那么堆序的保持和调整自然就是堆这类数据结构的核心
下面我们步入正题，我们已经基本了解了堆数据结构。
我们也知道堆的核心在于堆序的调整和保持，那么我们如何保持和调整堆的堆序性质呢？比如我们任意给定一个节点i如何保持以节点i为根的子堆的堆的性质呢，
我们提出 max_heap（Heap H,site i）例程，它是对最大堆进行操作的重要子程序，其输入为一个堆，和一个位置i。max_haeap(Heap H,sitei)被调用的时候我们假定以LEFT(i)和RIGHT(i)为根的两个子堆都是最大堆。但位置i可能并不满足最大堆性质，即i出的关键字可能小于其儿子的关键字。max_heap让位置i处的关键字在最大堆中“下降”，使以位置i为根的子树成为最大堆
伪算法如下： （伪代码有些我写的可能不是很规范）
Max_heap(heap , i)
L<-LEFT(i)
R<-RIGHT(i)
if L<=heap_size and heap[L]>heap[i]
thenlargest<-L
Else largest<-i
If R<=heap_size and heap[R]>heap[i]
Then largest<-R
If largest ！=i
Then exchange heap[i]<->heap[largest]
max_heap(heap,largest);
我们注意到这个算法是尾递归，我们可以很容易将它改成循环，这样可以节省程序反复调用的开销
这里给出该算法的循环实现：
max_heap(heap,i)
whike(i
do L<-LEFT(i);
R<-RIGHT(i)
If L<=heap-size and heap[L]>heap[i]
Thenlargest<-L
Else largest<-i
If R<=heap-sizeand heap[R]>heap[i]
Then largest<-R
If largest=i
//我们已经架设i节点的儿子均为最大堆，如果i也满足最大堆，那么以i为根的最大堆就满足堆性质，那么我们就不必继续循环下去，直接跳出循环即可
Break;
Else exchangeheap[largest]<->a[i]
i<-largest
我们给一个简单的图例让大家更好的理解
我们注意到位置i(位置2)并不满足最大堆的性质（但他的孩子节点满足最大堆性质），因此我们对位置i调用一次max_heap(heap, i(2)),于是关键字16和7调换了。有上面的算法我们知道i变成LEFT(2)即位置4，我们注意到位置4也不满足堆性质。所以我们递归调用一次max_hea（heap ,i(4)）,于是关键7和9调换。i变成RIGHT(i)即9。于是程序在这里结束。
对于这个算法我们容易看出位置i处的关键字在环的的情况下由它所在的层被“下降”到了底层。不难得出他的运行时间为O(h) （h为位置i所在的层） 跟一般的我们说这个算法的运行时间为O(lgn) (即最坏情况下他由一个n个元素组成的堆的根处被“下降”到了底层)。
到这里我们会想，我们有了max_heap，可是能做什么呢？如果我想建立一个堆那该怎么实现呢？
而且 在位置i处调用max_heap是有限制的，即位置i的孩子节点为根的堆必须满足堆性质，唯一可以允许的是位置i可以不满足堆性质。 在这么苛刻的条件下。我们如何有效的利用max_heap历程来实现建堆的目的呢？
要想实现实现建堆，我们还需要对完全二叉树的性质做简单的了解。通俗的说完全二叉树就是除了最后一层外其它层都达到最大节点数，而且最后一层节点都连续击中在最左边。我们需要了解的是完全二叉树的叶子节点的下标是n/2+1, n/2+2, n/2+3``````n。 （这里和下面的证明中 n/2为向下取整）
证明： 假设完全二叉树有n个节点，则最大节点的标号为n。
当为偶数时
节点n的父节点是n/2，则该父节点下一个节点是n/2+1，于是这个节点的做儿子为
(n/2+1)x2=n+2，即n/2+1节点的做儿子节点为n+2>n。故n/2+1节点无儿子节点，即它是叶节点。所以n/2+2 n/2+3……n均为叶子节点
同理可正当n为奇数时 有(n/2+1)x2 >=((n-1)/2+1)x2=n+1 >n故n/2+1为叶节点。则n/2+2 ,n/2+3.。。。n均为叶节点。
我们知道二叉堆本身就可以被视为一棵完全二叉树，所以二叉堆也满足这个性质。有了这个性质，我们就可以来构建堆了。我们先直接给出伪代码：
Build_max_heap (heap)
i<-heap_size/2;
while i>=1
domax_heap(heap,i);
i<-（i-1）;
伪代码很简练。下面我们就来说明这个算法的正确性
我们已经知道的是 ：
1:在位置 i 处调用max_heap的前提是以i 的儿子节点为根的子堆都必须满足堆性质,唯一允许的是以节点i处不满足（所以我们才需要调用max_heap来保持）
2 :二叉堆的叶子节点为n/2+1，n/2+2，n/2+3…….n. （n即为heap_size 是堆的大小）
回到算法，算法的第一部先将i 赋值为heap_size/2 ，因为heap_size/2后的节点均为叶子节点，也就是平凡最大堆（因为叶节点没有儿子，所以它必满足堆性质），所以满足调用max_heap的条件。调用max_heap结束后我们知道节点i 将满足最大堆性质（即以它为根的堆是满足最大堆性质的）
然后 i 减一，因为前一次的调用我们知道 现在 i 之后的节点依旧满足最大堆性质。这就构成了循环不变式，即每次调用max_heap后节点i , i+1, I+2…都满足了最大堆性质。
所以算法结束时 ，最后一次调用在位置 1 上所以我们得到 1,2,3,4,5.。。。。heap_size都满足最大堆性质。特别的 节点 1就是所有元素组成的最大堆的根。
这样我们便得到了 建立最大堆的方法。下面我们给出 一个简单的图例。
这是一个无序的堆，首先我们在i=n/2(向下取整)=5 处调用一次max_heap.但节点五处本来就满足最大堆性质，所以调用max_heap并未做任何工作。
然后i--,这时候在位置4处，我们注意到它不满足最大堆性质，且他的较大的儿子的关键字是14，所以节点4的关键字4和 它的儿子节点8的关键字14调换，之后节点4也满足了满足了最大堆性质。
继续 i--这时候到位置3，它也是不满足的，它较大儿子的关键字是9，所以我们将他们交换。现在节点3也满足了最大堆性质。
i--到位置2 调用max_heap,他和有较大关键字16的儿子节点5交换关键字，在调用的max_heao内部我们知道他是循环比较位置i和他的儿子节点的，所以2和16交换后，在max_heap内部函数发现2被换到位置5后还是比它的儿子6小，于是又将他和儿子的关键字交换，于是关键字2被交换到了底部
最后i--,我们来到堆的顶部，在位置1 处我们调用max_heap,按上面的分析，3依次和16，,14,7，交换
最终我们得到最终的这个堆，它就是我们要得到的一个最大堆。
到这里，我们终于达到了见堆的目的，我们利用了max_heap和完全二叉树的性质，用简练的代码建立了一个堆。但分析一个程序的好坏并不是看他的代码是否简练。或是是否容易理解。我们需要知道的是他的效率高不高，它是否值得我们去运用它。
现在 我们就来分析这个建堆程序的效率。
首先我们先抛开数学方面的精确分析，我们来尝试用一般性的分析。我们前面已经分析过在调用一次max_heap时的一般的时间界我们表示为O(lgn)，在我们这个算法中我们调用了n/2次，那么就是说他的时间界可能的表示是O(n*lgn)。尽管它是正确的。但他并不精确。（就像是我们说 2<3, 但同样2<1000）
我们更希望得到的是一个较为精确的时间界。
上面的历程中，我们对n个元素构成的堆只调用了n/2次max_heap.。而且这在每次调用时，max_heap并不是每次都做了实际工作。就像上面的图例在位置5调用时max_heap就没有做任何工作，但在位置1处的调用却将它下降到了最底层。所以说这种调用并不是每次都会用时O(lgn)。
实际上完全二叉树的结构性质也导致了上面情况的出现，应为几乎有3/4的元素都在树的0层和1层。他们或是不调用max_heap或是调用了max_heap最多也就是比较了2次（一次比较找到较大有关键字的儿子，另一次比较有较大关键子的儿子和该位置的的关键子的大小关系，如果该位置的关键字小就交换），交换了一次。只有1/4的元素我们可以说他们是一般的调用。
我们也在max_heap的伪代码中看到其实时间的开销集中在两次比较上一次是比较出较大儿子，另一次比较是该最大儿子与改节点。所以max_heap()的时间开销是与比较的次数成比较的。这里我也做了一次测试
五百个数据一组我们对其进行建堆操作。我们测试了一百次。
截图显示每次建堆比较的次数大约在600左右，500个数据每个数据平均比较了1.2次左右。
这也更直观的表现了，在建堆操作中每次调用max_heap的平均时间界其实是O(1)既是常数时间，那么建堆操作调用了n/2次，所以我们说 建堆操作的平均时间界是O(n).而不是O(nlgn)。
下面给出更精确的数学分析。
不过我们还是要先给出一些有用的结论：-个n元素的组成的堆的高度为lgn（向下取整）（前面已经分析），并且在任意高度h上至多有（向上取整）个节点
这里给出简单的证明：
对n个节点的二叉堆来说其叶子节点有 n/2(向上取整)个（前面我们已经分析过n/2+1,n/2+2….n都是叶子节点）。即高度0上的节点有n/2个（向上取整），那么高度为1的节点必是高度为0的节点的父节点，一个父节点有两个儿子节点（这里的父节点指的是完全二叉树中高度大于0的节点，其他树结构并不一定是这样）。即高度为1的节点个数为 (n/2)/2。以此类推高度为2的节点有（（n/2）/2）/2个，所以高度为h的节点个数至多有（向上取整）个。
另外到的结论有之前我们已经分析过的max_heao作用在高度为h上的节点的时间为O(h)和n个元素的堆构成的元素高度为lgn（向下取整）。.
这样我们就可以给出精确表达式了：
这样我们完成了建堆的时间分析，我们可以将一组数据利用build_max_heap将他们组织成一个最大堆。文章一开始我们就说过对于堆，我们想快速的得到的是这组数据中了最大值。好了，经过了build_max_heap，最大值已经在根上了即heap[1]上。那么我们想取走最大值只需要常数时间取走第一个元素即可，这里我们给出另一个历程delete_and_return_max(heap) ，它删除堆中的最大值并将这个值返回。
Delete_and_return_max(heap)
Max<-heap[1]
heap[1]<-heap[heap_size]
Heap_size<-heap_size-1
Max_heap(heap,1)
Return max
我们先将heap[1]保存在max中，然后将最后一个元素复制给heap[1]，这样最后一个元素heap[heap_size]我们就可以不需要了，因为heap[1]已经被复制为它。而且我们本来就删除了堆中的最大值，所以堆的大小要减一。
这里我们知道根处的堆性质被破坏了（当然以其他节点为根的子堆性质并未被破坏），因为本来在最底层的元素被调到了根处。所以我们调用一次max_heap来调整从而保持堆的性质，然后再返回我们需要的最大值max.
到这里我们应经大致对保持和调整堆的性质，和如何建立一个堆做了较为充分的解释。
那么我们掌握了这些，我们还可以做什么呢。这里我们介绍一下堆在 排序方面的应用。
为简单起见。我们就讨论正整数排序。
你应该已经发现一个比较直观的方法了，我们不是有delete_and_return_max么，这样我申请一个同样大小的数组。调用heap_size次delete_and_return_max每次调用都从后往前放置。这样我不就得到了一个升序排列的整数序列了。
当然这是个可行的办法，但我们还可以像到更好一点的办法。上面的方法虽然简单，但是它用了两倍的存储空间，你必须申请一个和堆一样大小的数组来存放排序后的数。
这里 我们利用一下delete_and_return_max中的思想。我们每次调用它后，他的最后一个位置我们都不用了，我们并没有真正释放它，而是让heap_size-1，通过这样使我们访问不到它。但它却是还在那里。所以我们可以充分利用这些访问不到的位置来存放我们取出来的元素。
我们给出伪代码
Heap_sort(heap)
Build_max_heap;
Size=heap_size; //保存heap_size大小
Fori<-size to 2
Doexchange heap[1]<->heap[heap_size]
Heap_size<-heap_size-1
Max_heap(heap,1)
Heap_size=Size //还原堆大小
我们先调用build_max_heap将这组元素建立成一个堆所.我们还需要保存heap_size.
然后我们在一个循环中执行类似delete_and_return_max的代码。每次现有的堆的最大值都被交换到最后。
这样就成功的将这组元素按升序排序了。
最后heap_size=1.这时我们访问不到后面已排序的元素了，所以需要还原heap_size.
我们依旧给出一个简单的图例。
这个过程模拟了一个最大堆（已经执行过建堆操作了）执行反复交换和调整的过程。为连接的数据表示我们已经访问不到了。
我们看到最后我们只能访问到位置1，其他都访问不到了。所以程序中需要回复堆大小这一步。
基于我们前面的分析。堆这段代码的运行时间分析已经很简单了。
执行Build_max_heap时间为O(n)
执行n-1次max_heap的时间为 （n-1）lgn ,
注意这里和前面的分析中max_heap调用平均用时为O(1)不一样，这里为此都在根除调用所以用时为lgn。你可能会说但是heap_size在减小啊。如果你精确的分析，你会发现n-1的调用大致是lgn！根据 斯特林近似公式我们知道n!=o(),所以运行时间为O(nlgn)
于是我们得到堆排序的运行时间界是O(nlgn)。
最后我们给出所有伪代码的程序实现
static void max_heap(Heap H,intsite)
{
if(site>H->current_size)
{
fprintf(stderr,"heapoverflow\n");
exit(EXIT_FAILURE);
}
intchild;
int_ttmp=H->array[site];
for(;site*2<=H->current_size;site=child)
{
child=site<<1;
/*如果右儿子存在*/
if(child+1<=H->current_size&&H->array[child+1]>H->array[child])
{
child++;
}
/*这里我们并没有真正的执行伪代码中的每次都交换，那样的话一次需要三次复制，
d次交换就需要3d次复制，而这里我们只需要d+1次复制操作
用到的是类似插入排序中的思想
*/
if(tmparray[child])
{
H->array[site]=H->array[child];
}
else
break;
}
H->array[site]=tmp;
}
void build_max_heap(Heap H)
{
if(is_empty(H))
{
fprintf(stderr,"youcan not on a empt heap to use build_max_heap\n");
exit(EXIT_FAILURE);
}
inti;
for(i=H->current_size/2;i>0;i--)
max_heap(H,i);
}
int_t delete_and_return_max(HeapH)
{
int_tmax=H->array[1];
H->array[1]=H->array[H->current_size];
H->current_size--;
max_heap(H,1);
returnmax;
}
void heap_sort(Heap H)
{
/*保存堆的大小*/
intcurrent_size_tmp=H->current_size;
inti=H->current_size;
for(;i>1;i--)
{
exchange(&H->array[1],&H->array[i]);
H->current_size--;
max_heap(H,1);
}
/*恢复堆大小*/
H->current_size=current_size_tmp;
}