二叉树
说到堆,首先要提一下二叉树。
根据数据结构的基础知识,可以知道二叉树分为完全二叉树和满二叉树,其中满二叉树很好理解,就是一棵除了最后一层没有子结点、其余每一层的所有结点都有两个子节点的二叉树,如下图:
满二叉树的结点数是同样深度的二叉树的结点数的最大值,所有叶子结点必须在同一层上。
完全二叉树又是什么呢?其实完全二叉树是从满二叉树上衍生出来的,官方定义是对于深度为K的,有N个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
但其实就我来说,第一遍读完全二叉树的定义是没有读懂的,所以我再把自己的理解用比较通俗的话说出来:完全二叉树就是只有最后一行没满的满二叉树,且最后一行的叶子结点都集中在左边。可以结合下图理解:
堆
堆是一种特殊的树,堆和树的区别在于,树不会对元素进行排序,而堆是遵循父结点小于子结点或父结点大于子结点的特殊的树,它的根结点的值是最大或最小的。
而我们平时经常提到的、以及经常应用的堆,如果不明确说明,其实都是说的二叉堆,从名字就可以看出来,二叉堆是从二叉树衍生来的,通过上面的描述我们已经知道二叉树分为满二叉树和完全二叉树,二叉堆就是一棵特殊的完全二叉树。
而特殊的点也就是上一段所说的,二叉堆的任意结点会全部大于或小于两个子结点,根结点会是所有结点的最大或最小值。
其中,将根结点最大的堆称为最大堆或大根堆,根结点最小的堆称为最小堆或小根堆。
需要特别注意一下的是,由于堆是由树实现的,而我们习惯用链表来实现树,所以自然会想到用链表来实现堆,实现是可以实现的,但是更推荐用数组来实现堆,这是因为就堆排序来说,如果用链表的实现方式,同样也可以实现,但是与数组相比每个结点的大小增大了(每个结点需要存储数据和指向子结点或父结点的指针),但是算法却没有得到优化,时间复杂度还是平均N*log2(N)(N为结点数),所以是没有必要的。
当然,有时候为了方便,我们也会直接使用集合来实现堆,具体还是要看需求场景。
下图为一个典型的数组实现堆:
堆排序
对二叉树和堆的基本概念了解之后,终于可以进入正题,那么什么是堆排序呢?其实堆排序就是不停的在做两件事:构建堆和取出根结点。这里我们使用最大堆来进行排序。
最复杂的部分是构建最大堆,根据上面的内容我们知道最大堆的特性是任意父结点的值大于两个子结点的值,所以构建最大堆的过程就是不停遍历堆中元素,将子结点大于父结点的地方进行一个父与子值的对换,然后将对换后的子结点再与子结点的子结点比较,依次执行下去。
根据上面的描述,不难想象到这是一个递归的过程,所以可以使用递归的方法来处理这个算法,但是由于递归对资源的消耗比较大,而且容易出现问题,所以这里我们单纯使用循环来实现了构建堆的maxHeapify方法,方法如下:
|
|
因为只是实现一个思路,所以这里选择了最直观的对正整数排序,方法实现的思路是传入要排序的数组和要排序的最后一个元素的位置,首先计算出最后一个父结点的位置,为什么要从最后一个父结点而不是最后一个结点的位置呢,因为我们选择的方法是依次比较父结点和两个子结点的大小,如果父结点小于其中某个子结点就进行一个值的对换,既然如此那些叶子结点本身没有子结点,也就没有从它们开始遍历的必要。
计算最后一个父结点的位置用到了位运算:
|
|
其实这个式子相当于(last-1)*2,就是一个完全二叉树从子结点位置求父结点位置的公式,之所以使用位运算而不是乘运算是因为位运算效率比普通乘除运算高大约3-5倍,所以后面也有其他的对位运算的使用。
之后我们用了一个point值等于父结点的位置,这个point相当于一个指针,这里虽然只是让它等于父结点的值,但后面它的作用其实是用来指示下一个父结点的位置。
之后就进入了用来代替递归的while循环中,循环中的实现思路简单来说就是根据现在的父结点获取到左子结点和右子结点,根据它们对应的位置从数组中获取到对应结点的值,然后进行一个大小比较,如果父结点的值小于左子结点,就将这两个结点的值进行交换,同理再将现在父结点的值与右子结点比较。这里需要注意的是右子结点是有可能不存在的,这里为了标示右子结点是否存在设了一个haveRight的波尔值:
|
|
因为这里示例是简单的对正数排序,所以我们直接对右子结点默认-1,后面的比较只要不小于它就说明右子结点存在(当然这还是不严密的)。
我们可以看到,不管是对左子结点还是右子结点进行比较,对应的代码段中都有一句对point的操作,这也就是这个循环用来代替递归的关键语句:
|
|
我们知道,根据之前的实现思路,如果是操作最后一个父结点,那么只需要对父结点和子结点进行一个简单的对调就可以结束对这个父结点的操作了,但是如果放到上层的父结点,事情就没这么简单,对第一层父结点与子结点进行对换之后,我们需要回过头去看被调换了值的子结点与这个子结点的子结点的大小比较。
有一点拗口啊,举个例子,有这样一个完全二叉树:
此时如果正在比较的父结点位置为1,则5与8和45分别比较,一轮比较之后变成下面的完全二叉树:
可以看到,父结点的5与两个子结点发生过对换后,新的子结点5和8与它们对应的子结点又发生了大小关系的变化,5比它的子结点7小,8比它的子结点11小,也就是说,发生过一次结点对换后,需要再将对换后的子结点与子结点的子结点进行大小比较,这时候point就可以发挥作用了,我们判断如果发生过一次对换并且对换后的子结点还有子结点,则将point指向对换后的子结点,标识这个子结点会作为下一次循环的父结点。具体实现便是上面的那两个if语句。
循环的最后,判断point是否和一开始的父结点位置相同,如果不同就说明发生了父结点与子结点的对换并且对换后的子结点还有子结点,也就让代表父结点位置的parentPos等于point,然后continue开始下一次循环。而如果point还与父结点位置相同,说明这个父结点没有与子结点发生对换或者发生了对换但是子结点没有下一层子结点,也就不需要去判断子结点与子结点的子结点的大小关系,这两种情况就可以直接让父结点和point的位置-1,直接开始对下一个父结点的比较。
上面是生成最大堆的操作,而堆排序是不断进行两个操作,除了生成最大堆,还要不断取出根元素,相比生成最大堆,取出根元素的操作就简单很多,只是一个值的对换:
|
|
也就是将根元素与last指向的最后一个元素位置相对换。
这两个方法完成之后,堆排序的操作就很简单了:
|
|
我们只需要传入需要排序的数组,先对整个数组构建最大堆,然后将根与最后一个值交换,然后将last往前移动一位,再对改换last值的数组进行一次构建堆,然后将新的根与last处的值交换。。。直到last指到根,这个数组也就完成了排序。