优先级队列（堆实现）

（一）优先级队列定义

（二）方法实现 

获得最大元素方法

去掉最大元素方法

 修改优先级方法

添加节点


 

（三）实现

/**
 * 用堆实现一个优先级队列
 * 主要是添加、修改、删除节点
 * 节点具有唯一性
 * @author HHF
 * 2014年11月28日
 */
public class PriorityQueue {

	public static int HEAPSIZE;
	public static void main(String[] args) {
		int[] array = Common.random(0,100,10);
		HEAPSIZE = array.length;
		build(array);//建一个极大堆
		System.out.println("原始数据：");
		Common.print(array);
	
		//获得最大值
		System.out.println("优先级最高的节点："+maximum(array));
		
		//获得并删除最大值
		System.out.println("将要被删除的优先级最高的节点："+extractMax(array));
		System.out.println("删除后的数据：");
		Common.print(array);
		
		//修改优先级
		increaseKey(array, 5, 100);
		System.out.println("修改后的数据：");
		Common.print(array);
		
		//添加节点
		insert(array, 101);
		System.out.println("插入后的数据：");
		Common.print(array);
		
		//删除节点
		System.out.println("删除的数据："+delete(array, 1));
		System.out.println("删除后的数据：");
		Common.print(array);
	}
	
	/**
	 * 返回优先队列中优先级最高的节点
	 * @param array
	 * @return
	 */
	public static int maximum(int[] array){
		return array[0];
	}
	
	/**
	 * 去掉并返回优先级队列中优先级最高的节点
	 * @param array
	 * @return
	 */
	public static int extractMax(int[] array){
		if(HEAPSIZE < 1){
			(new Exception("队列内无元素    ")).printStackTrace();
			return 0;
		}
		//获得最优节点
		int max = array[0];
		//删除最优节点
		array[0] = array[--HEAPSIZE];
		//整理堆
		heapify(array, 0);
		//返回最优节点值
		return max;
	}
	
	/**
	 * 往优先队列中插入节点
	 * 记得要去重
	 * @param array
	 * @param x
	 */
	public static void insert(int[] array, int x){
		array[HEAPSIZE++] = x-1;//加一个元素
		increaseKey(array, HEAPSIZE-1, x);
	}
	
	/**
	 * 将优先级为x的节点优先级修改为k
	 * @param array
	 * @param i被修改值下标
	 * @param k
	 */
	public static void increaseKey(int[] array, int i, int k){
		if(HEAPSIZE <= i){
			(new Exception("修改优先级节点下标有误  ")).printStackTrace();
			return;
		}
		if(k <= array[i]){
			(new Exception("新节点的优先级被改低了  ")).printStackTrace();
			return;
		}
		//优先级被修改了
		array[i] = k;
		//整理队列
		int parent = (i-1)/2; //父节点下标
		while(parent>-1 && array[parent]<array[i]){//到了必要交换子父节点的时候了
			Common.swap(array, parent, i);
			i = parent;
			parent = (i-1)/2;
		}
	}
	
	/**
	 * 将下标为i的节点删除 并返回其值
	 * @param array
	 * @param i
	 */
	public static int delete(int[] array, int i){
		if(HEAPSIZE <= i){
			(new Exception("删除节点下标有误  ")).printStackTrace();
			return 0;
		}
		//优先级被修改了
		int result = array[i];
		//整理队列
		array[i] = -1;
		heapify(array, i);
		HEAPSIZE--;
		return result;
	}
	
	/**
	 * 将array变成一个极大堆
	 * @param array 堆
	 */
	public static void build(int[] array){
		int size = array.length;
		for(int i=size/2-1; i>=0; i--){
			heapify(array, i);
		}
	}
	
	/**
	 * 前提是i的左右孩子子树均已经为正常极大堆
	 * 将i调整为正确位置
	 * @param array
	 * @param i 下标
	 */
	public static void heapify(int[] array, int i){
		int left = 2*i+1;//左孩子下标
		int right = left+1;//右孩子下标
		int large = 0;
		//选出left right 和  i 三个下标对应的最大值 记其下标为large 
		if(left<HEAPSIZE  && array[left] > array[i]){
			large = left;
		}else{
			large = i;
		}
		if(right<HEAPSIZE && array[right] > array[large]){
			large = right;
		}
		//准备发生交换 和 递推下一轮
		if(large != i){
			Common.swap(array, large, i);
			heapify(array, large);//此时的i所对应的值 已经 下移一层到了large
		}
	}
}

 （ps:附件内附上工具类Common.zip）