minheap.java

来自「<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关」· Java 代码 · 共 421 行

/*
 * Copyright (C) 2000-2007 Wang Pengcheng <[e-mail]>
 * Licensed to the Wang Pengcheng under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The LGPL licenses this file to You under the GNU Lesser General Public
 * Licence, Version 2.0  (the "License"); you may not use this file except in
 * compliance with the License.  You may obtain a copy of the License at
 *
 *     http://www.gnu.org/licenses/lgpl.txt
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package cn.edu.whu.iss.algorithm.unit06;

import mypackage.tools.print.P;

/**
 * The data structure of min heap
 * @author wpc
 * @version 0.0.1
 */
public class MinHeap {

	/**
	 * Sort descending the elements with the datastruct heap O(n lg(n) )
	 * 
	 * @param t
	 *            elements's list that will be sorted
	 * @return true sorted descending completely
	 */
	public static boolean heapSortDescending(int[] t) {
		try {
			MinHeap h = new MinHeap(t, true);
			for (int i = h.length() - 1; i > 0; i--) {
				h.exchange(0, i);
				h.setHeapSize(h.getHeapSize() - 1);
				h.minHeapify(0);
			}
			return true;
		} catch (Exception e) {
			e.printStackTrace();
			return false;
		}
	}

	public static void main(String[] args) {
		int[] a = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		MinHeap h = new MinHeap(a);
		MinHeap.heapSortDescending(a);
		for(int i=0;i<a.length;i++){
			P.rint(a[i]+" ");
		}P.rintln();
		P.rintln(h);

		P.rintln(h.heapDecreaseKey(3, 1));
		P.rintln(h);
		P.rintln(h.heapDecreaseKey(3, 10));
		P.rintln(h);
		P.rintln(h.heapExtractMin());
		P.rintln(h);
		P.rintln(h.heapExtractMin());
		P.rintln(h);
		P.rintln(h.heapExtractMin());
		P.rintln(h);
		P.rintln(h.heapExtractMin());
		P.rintln(h);

		P.rintln(h.minHeapInsert(5));
		P.rintln(h);
		P.rintln(h.minHeapInsert(10));
		P.rintln(h);
		P.rintln(h.minHeapInsert(11));
		P.rintln(h);
		P.rintln(h.minHeapInsert(12));
		P.rintln(h);
		P.rintln(h.minHeapInsert(-3));
		P.rintln(h);
		P.rintln(h.heapExtractMin());
		P.rintln(h);
		P.rintln(h.heapExtractMin());
		P.rintln(h);
		P.rintln(h.heapExtractMin());
		P.rintln(h);
		
		P.rintln(h.heapDelete(0));
		P.rintln(h);
		P.rintln(h.heapDelete(1));
		P.rintln(h);
		P.rintln(h.heapDelete(2));
		P.rintln(h);
		P.rintln(h.heapDelete(3));
		P.rintln(h);
		P.rintln(h.heapDelete(4));
		P.rintln(h);
		P.rintln(h.heapDelete(100));
		P.rintln(h);
	}

	private int heapSize;

	private int[] a;

	public MinHeap() {
		heapSize = 0;
	}

	public MinHeap(int[] t) {
		a = t.clone();
		heapSize = 0;
		buildMinHeap();
	}

	private MinHeap(int[] t, boolean f) {
		a = t;
		heapSize = 0;
		buildMinHeap();
	}

	/**
	 * Build max heap
	 * 
	 * @return true build completely
	 */
	public boolean buildMinHeap() {
		try {
			heapSize = a.length;
			for (int i = a.length >> 1; i >= 0; i--) {
				minHeapify(i);
			}
			return true;
		} catch (RuntimeException e) {
			e.printStackTrace();
			return false;
		}
	}

	/**
	 * Exchange the element l and r
	 * 
	 * @param l
	 *            element's number
	 * @param r
	 *            element's number
	 * @return true exchange completely
	 */
	public boolean exchange(int l, int r) {
		try {
			int temp = a[l];
			a[l] = a[r];
			a[r] = temp;
			return true;
		} catch (RuntimeException e) {
			e.printStackTrace();
			return false;
		}
	}

	/**
	 * Get the elements of the heap
	 * 
	 * @return elements
	 */
	public int[] getElements() {
		return a;
	}

	/**
	 * Get the heap size of this heap object
	 * 
	 * @return heap size
	 */
	public int getHeapSize() {
		return heapSize;
	}

	/**
	 * Get the elemet i's left child's number
	 * 
	 * @param i
	 *            element
	 * @return left child's number
	 */
	private int getLeftChild(int i) {
		return 2 * i + 1;
	}

	/**
	 * Get the element i's parent's number
	 * 
	 * @param i
	 *            element that needs getting parent's number
	 * @return parent's number
	 */
	private int getParent(int i) {
		if(i<=0){
			return 0;
		}
		else {
			return (i - 1) >> 1;
		}
	}

	/**
	 * Get the element i's right's number
	 * 
	 * @param i
	 *            element
	 * @return right's number
	 */
	private int getRightChild(int i) {
		return 2 * i + 2;
	}

	/**
	 * Delete element's i from heap
	 * @param i element's number
	 * @return true delete completely
	 */
	public boolean heapDelete(int i){
		try {
			if(i>heapSize){
				P.rintln("location i is bigger that current heapSize");
				return false;
			}else if(i<=0){
				P.rintln("location must be between [1,"+heapSize+"]");
				return false;
			}
			i--;
			a[i]=a[heapSize-1];
			a[heapSize-1]=Integer.MAX_VALUE;
			heapSize--;
			if(a[i]>=a[getParent(i)]){
				minHeapify(i);
			}else{
				while( (i>0)&&(a[getParent(i)]>a[i]) ){
					exchange(i,getParent(i));
					i=getParent(i);
				}
			}
			return true;
		} catch (RuntimeException e) {
			e.printStackTrace();
			return false;
		}
	}

	/**
	 * Get the min element in the heap and delete it
	 * 
	 * @return min element
	 */
	public int heapExtractMin() {
		if (heapSize < 1) {
			P.rintln("Heap underflow");
			return -1;
		}
		int min = a[0];
		a[0] = a[heapSize - 1];
		a[heapSize-1]=Integer.MAX_VALUE;
		heapSize--;
		minHeapify(0);
		return min;
	}

	/**
	 * Decrease the element[i] to the key
	 * 
	 * @param i
	 *            element's number
	 * @param key
	 *            new key
	 * @return true Decrease completely
	 */
	public boolean heapDecreaseKey(int i, int key) {
		try {
			if (key > a[i]) {
				P.rintln("New key is bigger than current key");
				return false;
			}
			a[i] = key;
			while ((i > 0) && (a[getParent(i)] > a[i])) {
				exchange(i, getParent(i));
				i = getParent(i);
			}
			return true;
		} catch (RuntimeException e) {
			e.printStackTrace();
			return false;
		}
	}

	/**
	 * Get the min heap 's smallest element
	 * 
	 * @return smallest element
	 */
	public int heapMinimum() {
		return a[0];
	}

	/**
	 * The length of the heap
	 * 
	 * @return heap's length
	 */
	public int length() {
		return a.length;
	}

	/**
	 * Keep characteristic of min-heap with the i as root
	 * 
	 * @param i
	 *            the root number
	 * @return true keep completely
	 */

	public boolean minHeapify(int i) {
		try {

			int l = getLeftChild(i);
			int r = getRightChild(i);

			int smallest;
			if ((l < heapSize) && (a[l] < a[i])) {
				smallest = l;
			} else {
				smallest = i;
			}

			if ((r < heapSize) && (a[r] < a[smallest])) {
				smallest = r;
			}

			if (smallest != i) {

				int temp = a[i];
				a[i] = a[smallest];
				a[smallest] = temp;

				return minHeapify(smallest);
			}

			return true;
		} catch (Exception e) {
			e.printStackTrace();
			return false;
		}
	}

	/**
	 * Insert new element to this heap
	 * 
	 * @param key
	 *            new element
	 * @return true Insert completely
	 */
	public boolean minHeapInsert(int key) {
		try {
			
			//I think this field is very important for us to learn the ArrayList class
			//Because it is as the same method to change the memory of an array's size
			//From this we can konw change the size of one array is very slow.
			/*
			 * 不愧是所谓的可变长数组,还好java这个玩意是的以引用为主要操作手段的,要不是那个内存转移的会非常麻烦,
			 * 采用引用的方法将数据量降到了最低.从原理上看这种可变长数组不能算什么新东西,不过是巧妙的隐人耳目的偷换的
			 * 内存空间.但是这个方法却方便的外部程序员的使用.
			 * 大致流程:在堆中申请一块新的足够大小的内存空间,将原来的拷贝过去,改变原引用指针,返回.
			 */
			if (heapSize >= a.length) {
				int[] t = new int[a.length];
				for (int i = 0; i < t.length; i++) {
					t[i] = a[i];
				}
				a = new int[t.length + 1];

				for (int i = 0; i < t.length; i++) {
					a[i] = t[i];
				}
				a[a.length - 1] = Integer.MAX_VALUE;
			}

			heapSize++;
			heapDecreaseKey(heapSize - 1, key);

			return true;
		} catch (RuntimeException e) {
			e.printStackTrace();
			return false;
		}
	}

	/**
	 * Reset the heap's size
	 * 
	 * @param heapSize
	 *            heapsize
	 */
	public void setHeapSize(int heapSize) {
		this.heapSize = heapSize;
	}
	
	public String toString() {
		String s = "";
		s += "Heapsize=" + heapSize;
		s += " ; Elements's length=" + a.length;
		s += "\n";
		s += "[";
		for (int i = 0; i < a.length - 1; i++) {
			s += a[i] + ",";
		}
		s += a[a.length - 1] + "]\n";
		return s;
	}
}