public class Heap {
	public static final int DEFAULTCAPACITY = 50;
	protected int[] storage;
	protected int size;
	
	public Heap() {
		this(DEFAULTCAPACITY);
	}
	
	public Heap(int dim) {
		storage = new int[dim];
		size = 0;
	}
	
	// l'utente dovrebbe usare array2heap
	protected Heap(int[] data) {
		storage = data;
		size = data.length;
		for(int i = getParentIndex(size-1); i >= 0; i--)
			heapify(i);
	}
	
	public void heapify(int i) {
		if(isLeaf(i))
			return;
		else {
			int j = 0; // inizializzazione fittizia per tacitare compilatore
			try {
				j = getMaxChildIndex(i);
			}
			catch(Exception e) {
				// qui non arriverą mai
			}
			if(storage[i] < storage[j]) 
				exchange(i, j);
			heapify(j);
		}
	}
	
	public int getMax() throws Exception {
		if(!isEmpty())
			return storage[0];
		else
			throw new Exception("getMax requested to empty heap");
	}
	
	public void delMax() {
		if(!isEmpty()) {
			storage[0] = storage[--size];
			heapify(0);
		}
	}
	
	public boolean insert(int k) {
		boolean doubled = false;
		if(isFull()) {
			doubleStorage();
			doubled = true;
		}
		storage[size] = k;
		int i = size++;
		int j = getParentIndex(i);
		while(!isRoot(i) && (storage[i] > storage[j])) {
			exchange(i, j);
			i = j;
			j = getParentIndex(i);
		}
		return doubled;
	}
	
	public boolean isLeaf(int i) {
		return getLeftIndex(i) >= size;
	}
	
	// non serve a niente.... solo per simmetria
	public boolean isRoot(int i) {
		return i == 0;
	}
	
	public boolean isEmpty() {
		return size == 0;
	}
	
	public boolean isFull() {
		return size == storage.length;
	}
	
	public static void heapSort(int[] data) {
		Heap aHeap = array2heap(data);
		for(int i = aHeap.size - 1; i > 0; i--) {
			aHeap.exchange(0, i);
			aHeap.size--;
			aHeap.heapify(0);
		}
	}
	
	public static Heap array2heap(int[] data) {
		return new Heap(data);
	}
	
	public String toString() {
		StringBuffer aString = new StringBuffer();
		for(int i = 0; i < size; i++)
			aString.append(storage[i]).append(" ");
		aString.append("-- capacity = " + storage.length);
		return aString.toString();
	}
	
	private static int getLeftIndex(int i) {
		return 2 * i + 1;
	}
	
	private static int getRightIndex(int i) {
		return getLeftIndex(i) + 1;
	}
	
	private static int getParentIndex(int i) {
		return (i - 1) / 2;
	}
	
	private boolean indexInHeap(int i) {
		return i < size;
	}
	
	private int getMaxChildIndex(int k) throws Exception {
		if(isLeaf(k))
			throw new Exception("children requested to a leaf");
		else {
			int l = getLeftIndex(k);
			int r = getRightIndex(k);
			int max = l;
			if(indexInHeap(r) && (storage[r] > storage[l]))
				max = r;
			return max;
		}
	}
	
	private void exchange(int i, int j) {
		int tmp = storage[i];
		storage[i] = storage[j];
		storage[j] = tmp;
	}
	
	private void printStorage() {
		for(int i = 0; i < storage.length; i++)
			System.out.print(" " + storage[i]);
		System.out.println();
	}
	
	private void doubleStorage() {
		int[] newstorage = new int[2 * storage.length];
		System.arraycopy(storage, 0, newstorage, 0, storage.length);
		storage = newstorage;
	}
}

 


Bacheca di Algoritmi e Strutture Dati a.a. 2007-08 - canale A - L

forum del corso

ultima modifica: 03/04/2008 23.35
by FdA