算法与数据结构（七）--堆

一.堆

1.堆的定义

堆是计算机科学中一类特殊的数据结构的通常，堆通常可以被看做是一颗完全二叉树的数组对象。

堆的特性

1.它是完全二叉树，除了树的最后一层结点不需要是满的，其他的每一层从左到右都是满的，如果最后一层结点不是满的，那么要求左满右不满。

2.它通常用数组来实现

具体方法就是讲二叉树的结点按照层级顺序放入数组中，根结点在位置1，它的子节点在位置2和3，而子节点的子节点则分别在位置4,5,6,7，以此类推。

如果一个结点的位置为k，则它的父结点的位置为【k/2】,而它的两个子结点的位置则分别为2k和2k+1。这样，在不适用指针的情况下，我们也可以通过计算数组的索引在书中上下移动：从a[k]向上一层，就令k等于k/2，向下一层就令k等于2k或2k+1。

3.每个结点都大于等于它的两个子结点，这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点，但这两个子结点的书序并没有做规定，更我们之前学习的二叉查找树是有区别的。

2.堆的API设计

3.堆的实现

【1】insert插入方法的实现

堆事用数组完成数据元素的存储的，由于数组的底层是一串连续的内存地址，所以我们要往堆中插入数据，我们只能往数组中从索引0处开始，依次往后存入数据，但是堆中对元素的顺序是有要求的，每一个结点的数据要大于等于它的两个子结点的数据，所以每次插入一个元素，都会使得堆中的数据顺序变乱，这个时候我们就需要通过一些方法让刚才插入的这个数据放入最合适的位置。

所以，如果往堆中新插入元素，我们只需要不断的比较新结点a[k]和它的父节点a[k/2]的大小，然后根据结果完成数据元素的交换，就可以完成堆的有序调整。

【2】delMax删除最大元素方法的实现

由堆的特性我们可以知道，索引1处的元素，也就是根结点就是最大的元素，当我们吧根结点的元素删除后，需要有一个新的结点的出现，这时我们可以暂时吧堆中最后一个元素放到索引1处，充当根结点，但是它有可能不满足堆的有序性需求，这个时候我们需要通过一些方法，让这个新的根结点放入到合适的位置。

所以当删除掉最后一个元素后，只需要将最后一个元素放到索引1处，并不断的拿着当前结点a[k]与它的子结点a[2k]和a[2k+1]中的较大者交换位置即可完成堆的有序调整。

4.堆排序

【1】实现步骤

1.构造堆；
2.得到堆顶元素，这个值就是最大值；
3.交换堆顶元素和数组中的最后一个元素，此时所有元素中的最大元素已经放到合适的位置；
4.对堆进行调整，重新让除了最后一个元素的剩余元素中额最大值放到堆顶；
5.重复2-4这个步骤，知道堆中剩一个元素为止。

【2】堆构造过程

堆的构造，最直观的想法就是另外再创建一个和新数组，然后从左网友遍历元素组，没得到一个元素后，添加到新数组中，并通过上浮，对堆进行调整，最后新的数组就是一个堆。
上述的方式虽然很直观，也很简单，但是我们可以用更聪明的一点的办法完成它。创建一个新数组，把原数组0~length-1的数据拷贝到新数组的1~length处，再从新数组长度的一半处开始往1索引处扫描（从右往左），然后对扫描到的每一个元素左下沉调整即可。