maxheap.java

用分支界限法解决的几个问题:包括0-1背包问题,最大团问题,电路布线问题,最大装载问题.作业最优处理问韪.

/**
 * 定义了一个大根的二分堆，以及堆上的一些基本操作和堆排序等等
 */

/**
 * @author rader 
 * @since jdk1.5
 * @date 1-3-2005
 */
package test;
public class Maxheap{
	final static int DEFAULT_CAPACITY = 200;// 堆的最大默认存储容量

	HeapNode[] array;   // 存储堆中的元素的数组

	int heapSize;// 堆中当前存储的元素的个数，即堆的长度

	/**
	 * 默认构造方法，做一些变量初始化工作； 要构造堆请调用buildMaxHeap方法，并传入一组整数
	 */
	public Maxheap() {
		heapSize = 0;
		array = new HeapNode[DEFAULT_CAPACITY + 1];// 第一位不存储元素，其默认值为0
	}

	/**
	 * 利用输入的整数集来构造出一个大根堆 MaxHeap
	 * 
	 * @param input
	 *            是一个整型数组
	 */
	public Maxheap(HeapNode[] input) {
		// heapSize=input.length;
		array = new HeapNode[DEFAULT_CAPACITY + 1];
		for (int i = 0; i < input.length; i++) {
			array[i + 1] = input[i];
		}
		buildMaxHeap(array);
	}

	/**
	 * 将任意输入的整数集构造成堆；时间复杂度为O(n)
	 */
	public void buildMaxHeap(HeapNode[] input) {
		heapSize = input.length;
		// this.array=input;
		for (int i = 0; i < input.length; i++) {
			array[i + 1] = input[i];
		}
		for (int i = (heapSize / 2); i >= 1; i--) {
			this.maxHeapify(i);
		}
		/** ********test begin******** */
		System.out.println("Build method is called...");
		System.out.println("The max heap is :");
		for(HeapNode e:array){
			System.out.print(String.valueOf(e)+" ");
		}
		System.out.println();
		/** ********test end******** */
	}

	/**
	 * 对当前的堆作调整，以使其满足大根堆的特性；时间复杂度为O(lgn)
	 * 
	 * @param startIndex
	 *            堆调整的起始位置
	 */
	public void maxHeapify(int startIndex) {
		int l = leftChild(startIndex);
		int r = rightChild(startIndex);
		int largest = startIndex;
		//int largest;
		if (l <= heapSize && array[l].upperProfit > array[startIndex].upperProfit) {
			largest = l;
		}
		/*******************/
		// else largest=startIndex;
		if (r <= heapSize && array[r].upperProfit > array[largest].upperProfit) {
			largest = r;
		}
		if (largest != startIndex) {
			exchange(startIndex, largest);
			maxHeapify(largest);
		}
	}

	/**
	 * 将整数插入到堆中;T(n)=O(lgn)
	 * 
	 * @param val
	 */
	public void insert(HeapNode val) {
		heapSize += 1;
		// 在堆中加入新的节点，并将其值设为最小的整数
		array[heapSize] = val;
	}

	/**
	 * 由于是大根堆，该操作先提取堆顶元素，然后将其从堆中删除并重新调整堆;T(n)=O(lgn)
	 * 
	 * @return 堆中的最大元素
	 */
	public double extractMax() {
		if (heapSize < 1)
			throw new NullPointerException("The heap is empty!");
		double max = array[1].upperProfit;
		array[1] = array[heapSize];
		heapSize -= 1;
		this.maxHeapify(1);
		return max;
	}

	/**
	 * 由于是大根堆，所以该操作返回堆顶元素;
	 * 
	 * @return 堆中的最大元素
	 */
	public double getMaximum() {
		return array[1].upperProfit;
	}
        public HeapNode removeMax(){
                if (heapSize < 1)
                throw new NullPointerException("The heap is empty!");
		HeapNode max = array[1];
		array[1] = array[heapSize];
		heapSize -= 1;
		this.maxHeapify(1);
                return max;
        }
	/**
	 * 增加堆中一个元素的值 ;T(n)=O(lgn)
	 * 
	 * @param position
	 *            元素所在的位置
	 * @param val
	 *            元素的新值
	 */
	public void increaseKey(int position, double val) {
		// 新值不能比原值小
		if (val < array[position].upperProfit)
			throw new UnsupportedOperationException(
					"The new value is smaller than its old value!");

		array[position].upperProfit = val;
		// 父节点的位置
		int parPos = parent(position);
		while (position > 1 && array[parPos].upperProfit < array[position].upperProfit) {
			exchange(position, parPos);
			position = parPos;
		}
	}

	/**
	 * @return 堆的大小，即堆中元素的个数
	 */
	public int getSize() {
		return heapSize;
	}

	public void setSize(int size) {
		heapSize = size;
	}

	/**
	 * 对堆进行排序;T(n)=O(nlgn)
	 */
      
        public HeapNode[] sort(HeapNode[] input){
	//int[] unsorted=input;
		buildMaxHeap(input);
		for(int i=heapSize;i>=2;i--){
			exchange(1,i);
			setSize(heapSize-1);
			maxHeapify(1);
		}
		
		/*******test begin******/
		System.out.println("Sort method is called...");
		/*******test end******/
		return array;
	}

	/**
	 * 返回第i个元素的左孩子的位置
	 * 
	 * @param i
	 * @return 第i个元素的左孩子的位置，/如果没有则返回-1
	 */
	private int leftChild(int i) {
		// if(2*i>heapSize)
		// return -1; //没有左孩子

		return 2 * i;
	}

	/**
	 * 返回第i个元素的右孩子的位置
	 * 
	 * @param i
	 * @return 第i个元素的右孩子的位置,如果没有返回-1
	 */
	private int rightChild(int i) {
		// if((2*i+1)>heapSize)
		// return -1; //没有右孩子

		return 2 * i + 1;
	}

	/**
	 * 返回第i个元素的父节点的位置
	 * 
	 * @param i
	 * @return 第i个元素的父节点的位置
	 */
	private int parent(int i) {
		return i / 2;
	}

	/**
	 * 交换堆中两个元素的位置
	 * 
	 * @param index_1
	 * @param index_2
	 */
	private void exchange(int index_1, int index_2) {
		HeapNode temp = array[index_1];
		array[index_1] = array[index_2];
		array[index_2] = temp;
	}
}