一、定义

计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。

二、特点

Heap是一种数据结构具有以下的特点:

1)完全二叉树;

2)heap中存储的值是偏序;

Min-heap: 父节点的值小于或等于子节点的值;
 

Max-heap: 父节点的值大于或等于子节点的值;

 

 

三、算法思想

不必将值一个个地插入堆中,通过交换形成堆。假设根的左、右子树都已是堆,并且根的元素名为R。这种情况下,有两种可能:

(1) R的值小于或等于其两个子女,此时堆已完成;

(2) R的值大于其某一个或全部两个子女的值,此时R应与两个子女中值较小的一个交换,结果得到一个堆,除非R仍然大于其新子女的一个或全部的两个。这种情况下,我们只需简单地继续这种将R“拉下来”的过程,直至到达某一个层使它小于它的子女,或者它成了叶结点。

四、筛选法

首先将要排序的所有关键码放到一棵完全二叉树的各个结点中(这时的完全二叉树并不具备堆的特性)。显然,所有的结点Ki都没有子女结点,因此以这样的Ki为根的子树已经是堆,然后从 的结点Ki开始,逐步把以为根的子树排成堆,直到以K0为根的子树排成堆,就完成了建堆过程。

在考虑将以Ki为根的子树排成堆时,以Ki+1,Ki+2,…,Kn-1为根的子树已经是堆,所以这时如果有Ki≤K2i+1和Ki≤K2i+2,则不必改变任何结点的位置,以Ki为根的子树就已经是堆;否则就要适当调整子树中结点的位置以满足堆的定义。由于Ki的左、右子树都已经是堆,根结点是堆中最小的结点,所以调整后Ki的值必定是原来K2i+1和K2i+2中较小的一个。不妨假定K2+1较小,将Ki与K2i+1交换位置,这样调整后Ki≤K2i,Ki≤K2i+1,并且以K2i+2为根的子树原来已经是堆,不必再作任何调整,只有以K2i+1为根的子树由于K2i+1的值已经发生变化(与Ki交换了),所以有可能不满足堆的定义(当K2i+1的左、右子树已经是堆)。这时可重复上述过程,考虑将K2i+1以为根的子树排成堆。如此一层一层递推下去,最多可以一直进行到树叶。由于每步都保证将子树中最小的结点交换到子树的根部,所以这个过程是不会反馈的。它就像过筛一样,把最小的关键码一层一层选择出来。

五、建堆效率

n个结点的堆,高度d =log2n。根为第0层,则第i层结点个数为2i,考虑一个元素在堆中向下移动的距离。大约一半的结点深度为d-1,不移动(叶)。四分之一的结点深度为d-2,而它们至多能向下移动一层。树中每向上一层,结点的数目为前一层的一半,而子树高度加一。

这种算法时间代价为Ο(n)

由于堆有log n层深,插入结点、删除普通元素和删除最小元素的平均时间代价和时间复杂度都是Ο(log n)。

六、操作

(1)build:建立一个空堆;

 

(2)insert:向堆中插入一个新元素;

 

(3)update:将新元素提升使其符合堆的性质;

 

(4)get:获取当前堆顶元素的值;

 

(5)delete:删除堆顶元素;

 

(6)heapify:使删除堆顶元素的堆再次成为堆。

七、代码

那么我们开始讲解操作过程吧,我们以小根堆为例

   刚刚那组未处理过的数据中我们很容易就能看出,根节点1元素8绝对不是最小的

   我们很容易发现它的一个儿子节点3(元素2)比它来的小,我们怎么将它放到最高点呢?很简单,直接交换嘛~~

   但是,我们又发现了,3的一个儿子节点7(元素1)似乎更适合在根节点。

   这时候我们是无法直接和根节点交换的,那我们就需要一个操作来实现这个交换过程,那就是上浮 shift_up

   操作过程如下:

   从当前结点开始,和它的父亲节点比较,若是比父亲节点来的小,就交换,然后将当前询问的节点下标更新为原父亲节点下标;否则退出。 

      模拟操作图示:

                

      伪代码如下:

Shift_up( i )
{
    while( i / 2 >= 1)
    {
        if( 堆数组名[ i ] < 堆数组名[ i/2 ] )
        {
            swap( 堆数组名[ i ] , 堆数组名[ i/2 ]) ;
            i = i / 2;
        }
        else break;
}

 

      这一次上浮完毕之后呢,我们又发现了一个问题,貌似节点3(元素8)不太合适放在那,而它的子节点7(元素2)

    好像才应该在那个位置。

      此时的你应该会说:“赐予我力量,让节点7上浮吧,我是ACMer!”

      然而,上帝(我很不要脸的说是我)赐予你另外一种力量,让节点3下沉!

      那么问题来了:节点3应该往哪下沉呢?

      我们知道,小根堆是尽力要让小的元素在较上方的节点,而下沉与上浮一样要以交换来不断操作,所以我们应该

    让节点7与其交换。     

      由此我们可以得出下沉的算法了:   

      让当前结点的左右儿子(如果有的话)作比较,哪个比较小就和它交换,

    并更新询问节点的下标为被交换的儿子节点下标,否则退出。

      模拟操作图示:

                

      伪代码如下:

Shift_down( i , n )    //n表示当前有n个节点
{
    while( i * 2 <= n)
    {
        T = i * 2 ;
        if( T + 1 <= n && 堆数组名[ T + 1 ] < 堆数组名[ T ])
            T++;
        if( 堆数组名[ i ] < 堆数组名[ T ] )
        {
           swap( 堆数组名[ i ] , 堆数组名[ T ] );
            i = T;
        }
        else break;
}

 

      讲完了上浮和下沉,接下来就是插入操作了~~~~

      我们前面用的插入是直接插入,所以数据才会杂乱无章,那么我们如何在插入的时候边维护堆呢?

    其实很简单,每次插入的时候呢,我们都往最后一个插入,让后使它上浮。

      (这个不需要图示了吧…)

      伪代码如下:

Push ( x ) {
        n++;
        堆数组名[ n ] = x;
        Shift_up( n );
}

      咳咳,说完了插入,我们总需要会弹出吧~~~~~

      弹出,顾名思义就是把顶元素弹掉,但是,弹掉以后不是群龙无首吗??

      我们如何去维护这堆数据呢?

      稍加思考,我们不难得出一个十分巧妙的算法:

    让根节点元素和尾节点进行交换,然后让现在的根元素下沉就可以了!

      (这个也不需要图示吧…)

      伪代码如下:

Pop ( x ){
        swap( 堆数组名[1] , 堆数组名[ n ] );
        n--;
        Shift_down( 1 );
}

      接下来是取顶…..我想不需要说什么了吧,根节点数组下标必定是1,返回堆[ 1 ]就OK了~~

    注意:每次取顶要判断堆内是否有元素,否则..你懂的

      图示和伪代码省略,如果你这都不会那你可以重新开始学信息学了,当然如果你是小白….这种稍微高级的数据

    结构还是以后再说吧。

      说完这些,我们再来说说堆排序。之前说过堆是无法以数组下标的顺序来来排序的对吧?

      所以我个人认为呢,并不存在堆排序这样的操作,即便网上有很多堆排序的算法,但是我这里有个更加方便的算法:

    开一个新的数组,每次取堆顶元素放进去,然后弹掉堆顶就OK了~

 

      伪代码如下:

Heap_sort( a[] )
{
        k=0;
        while( size > 0 )
        {
            k++;
            a[ k ] = top();
            pop();    
        }        
}

      堆排序的时间复杂度是O(nlogn)理论上是十分稳定的,但是对于我们来说并没有什么卵用。

      我们要排序的话,直接使用快排即可,时间更快,用堆排还需要O(2*n)空间。这也是为什么我说堆的操作

    时间复杂度在O(1)~O(logn)。

八、例题

https://www.luogu.org/problemnew/show/P2085(题解:https://blog.csdn.net/weixin_43272781/article/details/88425544

http://codevs.cn/problem/1063/

九、参考文章

https://www.cnblogs.com/wangchaowei/p/8288216.html

https://www.cnblogs.com/chenweichu/articles/5710567.html

https://www.cnblogs.com/JVxie/p/4859889.html