堆

这种数据结构。一般堆用来实现优先级队列。优先级队列：和通常的栈和队列一样，只不过里面的每个元素都有一个“优先级”，在处理的时候，首先处理优先级最高的。通常包含三个操作getMax/delMax/insert

栈和队列算是优先级队列的特例。

使用其他数据结构均不能同时在O(lgn)的复杂度下完成。至少有一种操作要耗时O(nlgn).比如链表的插入操作O(1)，但是获取最大值必须遍历链表。

可以使用BBST以上三个操作达到最好的时间复杂度O(lgn)。事实上没必要用那么高端的数据结构来实现如此简单的功能，因为这里毕竟只需要这三个简单的功能而已。

于是堆这种数据结构应运而生。

堆在逻辑上是一颗完全二叉树（平衡因子处处非负的AVL树），在物理上直接借助向量(可变数组)，因此具有向量的形，树的神。

堆就是在向量的元素间定义了父子关系。

最大堆：所有节点的值均小于等于父节点，最小堆则反之。如下图为一个最大堆，我这里以最大堆为例。

构造这样的一个数据结构，上述三个接口的时间复杂度均为O(h)，由于完全二叉树的树高为O(lgn)，于是有getMax，delMax，insert的时间复杂度均为O(lgn)

在下面的代码中我没有使用向量，而是自己维护了一个数组，可以达到相同的效果。

堆的实现

public class Heap {
	private static int PARENT(int i){
		return (i-1)>>1;
	}
	private static int LEFT(int i){
		return 1+(i<<1);
	}
	private static int RIGHT(int i){
		return (i+1)<<1;
	}
	private int[] heapArray;
	private int n;
	public Heap(int MAX_SIZE) {
		heapArray = new int[MAX_SIZE];
	}
	
	/**
	 * 获得堆中最大值
	 * @return
	 */
	public int getMax(){
		if (n == 0) {
			throw new IndexOutOfBoundsException();
		}
		return heapArray[0];
	}
	
	/**
	 * 删除堆中最大值
	 */
	public void deleteMax() {
		if (n == 0) {
			throw new IndexOutOfBoundsException();
		}
		heapArray[0] = heapArray[n-1];
		n--;
		percolateDown(0);
	}
	
	/**
	 * 插入操作
	 * @param e
	 */
	public void insert(int e) {
		heapArray[n++] = e;
//		percolateUP(n-1);
		percolateUPRecu(n-1);
	}
	
	/**
	 * 上溢
	 * @param target  表示要进行上溢操作的元素的下标
	 */
	private void percolateUP(int target) {// 完全二叉树树高控制在O(lgn)  上溢的时间复杂度O(lgn)   3lgn---->  lgn+2
		int parent = PARENT(target);
		while (target > 0) {// target最多上溢到根
			if(heapArray[target] <= heapArray[parent]) 
				break;
			swap(heapArray,parent,target);
			target = parent;
			parent = PARENT(target);
		}
	}

	/**
	 * 递归上溢
	 * @param target 表示要进行上溢操作的元素的下标
	 */
	private void percolateUPRecu(int target) {
		if (target > 0) {
			if (heapArray[target] > heapArray[PARENT(target)]) {
				swap(heapArray,PARENT(target),target);
				percolateUPRecu(PARENT(target));
			}
		}
	}

	/**
	 * 下滤
	 * @param target  表示要进行下滤操作的元素的下标
	 */
	private void percolateDown(int target) {
		int maxIndex = maxOfThree(heapArray,target);
		while (target !=  maxIndex) {// 当target不是和两个孩子比起来最大的就一直下滤
			swap(heapArray,maxIndex,target);
			target = maxIndex;
			maxIndex = maxOfThree(heapArray,target);
		}
	}
	
	/**
	 * Floyd创建堆  自下而上的下滤    复杂度为O(n) 求和height(i)
	 * @param heapArr
	 */
	public void createHeapFloyd(int [] heapArr){ 
		System.arraycopy(heapArr,heapArray,heapArr.length);
		n = heapArr.length;
		for (int i = (n - 1) >> 1; i >= 0; i--) {
			percolateDown(i);
		}
	}
	
	/**
	 * 创建堆  自上而下的上溢    复杂度为O(nlgn) 求和depth(i)
	 * @param heapArr
	 */
	public void createHeap(int[] heapArr) {
//		for (int i : heapArr) {
//			insert(i);
//		}
		// 更紧凑的写法
		System.arraycopy(heapArr,heapArr.length);
		n = heapArr.length;
		for (int i = 0; i < n; i++) {
			percolateUP(i);
		}
	}
	
	/**
	 * 获取target以及它的两个孩子中的对应值最大的下标
	 * @param heapArray
	 * @param target
	 * @return  返回target以及它的两个孩子中的对应值最大的下标
	 */
	private int maxOfThree(int[] heapArray,int target) {
		// 比较target和他的两个孩子的大小，返回最大的下标
		// 有效下标不能超过n-1
		int left = LEFT(target);// > n-1 ? Integer.MIN_VALUE : LEFT(target);
		int right = RIGHT(target); // > n-1 ? Integer.MIN_VALUE : RIGHT(target);
		int max = target;
		if (left<=n-1) {
			max = heapArray[left] > heapArray[max] ? left : max;
		}
		if (right<=n-1) {
			max = heapArray[right] > heapArray[max] ? right : max;
		}
		return max;
	}
	
	private void swap(int[] heapArray,int i,int j) {
		int temp;
		temp = heapArray[i];
		heapArray[i] = heapArray[j];
		heapArray[j] = temp;
	}
}

其中每个方法的具体意思已经做了详细的注释。

相关算法

下面关于上溢和下滤的算法和创建堆的算法做以解释。

上溢

当插入一个新的元素时，我们首先将这个新元素放在数组的最后，然后将其与逻辑上的父亲节点比较，如果大于父亲节点，则一直重复交换，直到满足最大堆的条件或者已交换到树根位置，具体的可参考下图

下滤

（编辑：PHP编程网 - 黄冈站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!