/* * Created on 09/06/2003 */ package heap; /** * @author André Santanchè */ public class BinaryHeap implements MinimumHeap { protected HeapElement a[]; public BinaryHeap() { a = new HeapElement[0]; } protected int parent(int i) { // foi feito um ajuste para a posicao 0 do java return (i - 1) / 2; // o java calcula o piso quando a divisao eh inteira } protected int left(int i) { return 2 * i + 1; // foi feito um ajuste para a posicao 0 do java } protected int right(int i) { return 2 * i + 2; // foi feito um ajuste para a posicao 0 do java } protected void swap(int x, int y) { HeapElement aux = a[x]; a[x] = a[y]; a[y] = aux; a[x].setIndex(new Integer(x)); a[y].setIndex(new Integer(y)); } protected void minHeapfy(int i) { int l = left(i), r = right(i), min; if (l < a.length && a[l].getKey() < a[i].getKey()) min = l; else min = i; if (r < a.length && a[r].getKey() < a[min].getKey()) min = r; if (min != i) { swap(i, min); minHeapfy(min); } } public void buildMinHeap(HeapElement elem[]) { a = elem; for (int j = 0; j < a.length; j++) a[j].setIndex(new Integer(j)); for (int i = (a.length-1)/2; i >= 0; i--) minHeapfy(i); } public HeapElement heapMinimum() { if (a.length == 0) return null; else return a[0]; } public HeapElement heapExtractMin() { if (a.length < 1) { System.out.println("heap underflow"); return null; } HeapElement min = a[0]; a[0] = a[a.length - 1]; a[0].setIndex(new Integer(0)); // diminui tamanho do vetor HeapElement na[] = new HeapElement[a.length - 1]; System.arraycopy(a, 0, na, 0, a.length - 1); a = na; minHeapfy(0); return min; } public void decreaseKey(int i, int key) { if (key > a[i].getKey()) System.out.println("invalid new key"); else { a[i].setKey(key); while (i > 0 && a[parent(i)].getKey() > a[i].getKey()) { swap(i, parent(i)); i = parent(i); } } } public void decreaseKey(HeapElement el, int key) { decreaseKey(((Integer)el.getIndex()).intValue(), key); } public boolean isEmpty() { return (a == null || a.length == 0); } public void heapInsert(HeapElement el) { // aumenta tamanho do vetor HeapElement na[] = new HeapElement[a.length + 1]; System.arraycopy(a, 0, na, 0, a.length); a = na; int key = el.getKey(); el.setKey(Integer.MAX_VALUE); el.setIndex(new Integer(a.length - 1)); a[a.length - 1] = el; decreaseKey(a.length - 1, key); } public void heapDelete(HeapElement el) { int key = el.getKey(); decreaseKey(el, -1); heapExtractMin(); el.setKey(key); } public HeapElement elementAt(int i) { return a[i]; } public void setElement(int i, HeapElement el) { a[i] = el; } public String toString() { String r = ""; if (a != null) { r += a[0].getKey(); for (int i = 1; i < a.length; i++) r += ", " + a[i].getKey(); } return r; } }