堆相关操作复杂度分析

堆的层数

堆由一颗完全二叉树组成
那么n个结点的完全二叉树有log2(n+1)层,近似等于log2n

解释一下为什么log2n层?
第一层2^0个元素
第二层2^1个元素
第三层2^2个元素
第h层2^(h-1)个元素
利用等比数列求和公式:2^0+ 2^1+ 2^2+… +2^(h-1) =1x(1-2 ^ h) / (1-2) = (2^h)-1个元素

这是等比数列求和公式:a1=2^0=1,q=2,n=h,带入即可!
所以(2^h)-1=n ------> 2^h=n+1---->h=log2(n+1)≈log 2n

满二叉树叶节点个数:2^(h-1)个如果n个结点那么也就是n/2个叶节点

非叶节点个数和=总结点数-叶节点数=(2^ h-1)- (2^ (h-1))=2^ (h-1)-1 ≈2^ (h-1)=叶节点个数

通过这个规律:叶节点数等于非叶结点数
我们可以得出
倒数第二层结点数=n/4=n/2^(1+1)
(我们不看叶结点那层,那么除去叶节点的新满二叉树有n/2个结点,那么新的满二叉树的叶节点有n/4个元素,放在原来的满二叉树也就是倒数第二层结点数也就是n/4)

倒数第三层n/8=n/2^(2+1)
············
我们可以通过这个规律的出一般规律:任意下面有h层则此层有n/2^(h+1)个结点

堆相关操作复杂度

一、向堆中添加元素(sift up) O(logn)

解释如何添加元素
我们将元素插入到堆的尾部,也就是完全二叉树的最后一个结点,然后与它的父亲结点进行比较,如果是最大堆,那么该元素比父亲元素大,就swap交换位置,以此类推每次只要比父亲结点元素值大就交换,最坏要交换到堆顶,那么n个元素的堆最坏要交换log2n次也就是完全二叉树的高度h次,所以向堆中添加元素的复杂度O(logn)

二、向堆中删除元素(sift down) O(logn)

解释如何删除元素
以最大堆为例,我们每次只能删除堆顶元素,我们不能直接从堆顶拿出来,需要先交换堆顶元素与堆尾元素的位置,然后删除堆尾元素,那么堆顶元素可能不满足最大堆的性质,我们在下沉操作也就是sift down,每次只要该元素小于两个儿子结点元素的值,我们就取出较大的儿子结点与该元素交换位置,依次类推最坏要交换到堆底,也就是从第h层交换到第1层,有n个元素需要log2n次操作,所以复杂度O(logn)

三、利用堆排序 O(nlogn)

解释如何利用堆排序
我们可以把要排序的元素全部放入堆中,每次取出最大或者最小的元素即可,那么每次扔进堆,就需要sift up一次sift up需要O(logn)那么一共n个元素,所以利用堆排序的复杂度为O(nlogn)!

四、普通版本的原地成堆O(nlogn)

解释如何原地成堆
原地成堆的原理和利用堆排序原理相同,都是将元素直接扔到堆里,元素在sift up所以复杂度为O(nlogn)!

五、heapify原地成堆O(n)

解释如何heapify原地成堆
我们可以把未成堆的所有元素直接看成一个完全二叉树,我们找到最后一个非叶子结点,然后从最后一个非叶子结点进行sift down操作,也就是开始时,从倒数第二层开始进行sift down那么每个元素最多交换1次就可以。则倒数第三层需要(n/8)*2次操作,那么第四层需要(n/16)*3以此类推,下面有h层需要(n/2^(h+1))*h次操作,我们对这些操作做加和,可以得出一个公式:

在这里插入图片描述