介绍
堆是一种数据结构,它是一颗完全二叉树。最大堆则是在堆的基础增加了新的规则,它的根结点的值是最大的,而且它的任意结点的父结点的值都大于或者等于其左右结点的值。
代码
把堆看做一颗树的数组对象,相对于任意的一个结点(i),它都满足以下3个特性,如果它存在左右结点的话,那么其左结点的位置就i*2,右结点就是i*2 +1,父结点就是i/2。
定义一个最大堆的模板类max_stack,默认它的初始大小为DEFAULT_SIZE=1024,采用c++中容器vector来代表堆(方便扩展),length_表示堆的长度。
当往堆里面插入一个数据时,先判断当前堆长度是否已经等于默认长度,如果等于,则把容器的长度扩大一倍。然后把数据插入到数组的最后一位,用heap_increase_key方法移动它的位置。
heap_increase_key方法表示把i的原来的值替换成t值。然后递归和它的父结点做比较,如果比父结点值大,则它的值就和父结点做交换,如果小于,则递归结束,当前的i值就是它的位置。
获取最大堆的最大值,就是返回它的根结点的值。
返回最大堆的最大值,并且删除最大值,则需要重新计算出当前堆的最大值。其中的max_heapify方法就是对某个结点求最大堆的过程。
max_heapify方法是对某个结点求最大堆的过程:首先求出当前结点的左右结点,并判断左右结点和当前结点中最大那个结点的值,如果当前结点不是最大的那个值,则把最大结点的值和当前结点的值进行交换,然后递归去判断交换以后的值和它的左右结点的值的大小,如果当前结点的值就是最大值,则递归结束。
build_max_heapify是一个建堆的过程,只需要对0-length/2调用max_heapify方法进行求最大堆的过程就可以了,因为length/2以后的都是子节点(由left,right方法可知),都会经过求最大堆的过程。
堆排序是建立在堆的基础上的,所以首先得建立一个堆,然后再排序。排序的过程:每次都把当前最小的结点和数组的末尾的结点值进行交换,交换完成以后减少堆的长度,然后对当前堆进行一个求最大堆的过程,又求出一个最大堆以后,重复刚刚动作,直至整个堆的结束。这样,一个倒序排序的数组就出来了,通过print函数就可以输出整个数组。
最大堆代码的测试用例:
总结
堆分2种,最大堆和最小堆,其实最小堆的实现和最大堆基本一样。最大堆的根是最大值,而最小堆的根是最小值,在某些判断上符号改变下就是最小堆了。最大堆的作用有很多,比如排序,比如事件驱动,某个需要判断整个数据当中,其中的最大值是否满足条件时,进行什么操作等等。需要了解更多的编程和算法问题,请关注我,谢谢。