堆与堆排序
一、什么是堆
堆其实是一颗完全二叉树,除了树的最后一层不是满的,其他层从左到右都是满的。堆中除叶子节点外每个节点的关键字都大于等于(或小于等于)他的左右孩子的关键字,其中节点的关键字都大于等于左右孩子的关键字的堆称之为“大顶堆”或“最大化堆”,如下图a;节点的关键字都小于等于左右孩子的关键字的堆称之为“小顶堆”或“最小化堆”,如下图b。
二、堆的实现
因为堆是完全二叉树的结构,所以常用数组来进行实现堆。一般把根节点放在数组下标是0的位置,则i位置节点的数组下标则是(i-1)/2;i节点的左右孩子节点的数组下标为2*i+1和2*i+2。(如果根节点从1开始,则左右孩子节点数组下标是2*i和2*i+1)。
如图是一种大顶堆的数组存储及结构图。
二、堆的调整操作
堆的调整分为向上筛选和向下筛选(都是以大顶堆为例)。
向上筛选:
如果对节点i进行向上筛选,就是比较i节点的值与其父节点值的大小,如果该节点值比其父节点的值大,则这两个节点交换,再拿交换后的这个节点与其父节点比较,依次往上,直到该节点的值比其父节点的值小时或者该节点成为了根节点时结束。
向下筛选:
如果对节点i进行向下筛选,就是比较i节点的值与其左右孩子节点值的大小,如果三者中最大的值不是i节点,则i节点与其中值最大的节点进行位置交换(如果只有一个孩子节点,则二者比较再交换),再拿交换后的该节点与其左右孩子节点比较,依次往下,直到该节点的值比起左右孩子的值都大时或者该节点成为叶子节点时结束。
三、堆的建立
两种建立方式(都是以大顶堆为例)
1、不断添加元素进行建堆
每添加一个元素需要进行一次堆的调整,以保证堆结构。添加到第n个节点时,就对n节点进行向上筛选,这样即使添加了一个较大的元素,通过向上筛选,会把其位置往上调整,这样就保证了堆的结构。
时间复杂度:添加第一个元素是最差情况下比较0次,第二个元素时最差情况下比较1次,第三个元素时比较1次……其实每添加一个元素就是比较该节点的深度-1次,即(根节点从0开始)第n个节点需要比较log2(n) 次,所以时间复杂度为O(log2(1)) + O(log2(2)) + O(log2(3))+…..O(log2(n)) = n log2(n)
证明过程我在纸上证明了,以下附上图片
2、把一个数组直接转换成堆
如果是将数组A转化成一个大顶堆。思想是,先找到堆的最后一个非叶子节点(即为第n/2个节点),然后从该节点开始,从后往前逐个调整每个子树,使之称为堆,最终整个数组便是一个堆。子数组A[(n/2)+1..n]中的元素都是树中的叶子,因此都可以看作是只含有一个元素的堆。
时间复杂度:第n/2 个节点最差情况下向下筛选比较1次,第n/2 – 1个及其节点最差情况下向下筛选比较其log2(n)- 其深度 次,所以时间复杂度与上类似,为(n/2)/2*1+(n/2)/4*2+….1*log2(n)=nlog(n)。所以两种插入方法的时间复杂度是相同的。
三、堆的移除操作
移除指的是移除堆的根节点(根节点的关键字是堆中所有节点关键字中的最大值或最小值),就是数组中索引为0的节点, 但是一旦移除根节点树就不是完全的了,数组中的0位置空出来了。所以为了在移除后仍然保持堆结构,我们需要做一定的调制操作。
概括移除操作分三步完成(以大顶堆为例):
第一步,移走根节点;
第二步,把最后一个节点移到根的位置;
第三步,向下筛选该节点。
这个过程也叫做“向下筛选”。
四、堆的插入节点操作
插入一个节点还是比较简单的。开始时把节点插入到数组中最后一个空着的单元中,而后向上筛选到合适位置,使得它在一个大于它的节点之下,在一个小于它的节点之上。
五、Java实现堆及其操作的代码
package data_structure;
import java.util.Random;
/**
* 堆的实现
* @author qihuijie
*/
public class Heap {
private Node[] heapArray; //存储堆节点的数组
private int maxSize; //堆节点的最大值
private int currentSize; //当前堆的大小
public Heap(int mx) { //完成一些初始化操作
maxSize = mx;
currentSize = 0;
heapArray = new Node[maxSize];
}
public boolean isEmpty(