Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package alda.dheap;
- public class DHeap<AnyType extends Comparable<? super AnyType>> {
- /**
- * Construct the binary heap.
- */
- int children; //Number of children allowed (d)
- private static final int DEFAULT_CAPACITY = 10;
- private int currentSize; // Number of elements in heap
- private AnyType[] array; // The heap array
- public DHeap() {
- this(DEFAULT_CAPACITY);
- this.children = 2;
- }
- /**
- * Construct the binary heap.
- *
- * @param capacity the capacity of the binary heap.
- */
- // public DHeap( int capacity )
- // {
- // currentSize = 0;
- // array = (AnyType[]) new Comparable[ capacity + 1 ];
- // }
- public DHeap(int d) {
- if (d > 1) {
- this.children = d;
- } else {
- throw new IllegalArgumentException();
- }
- array = (AnyType[]) new Comparable[d];
- }
- /**
- * Construct the binary heap given an array of items.
- */
- public DHeap(AnyType[] items) {
- currentSize = items.length;
- array = (AnyType[]) new Comparable[(currentSize + 2) * 11 / 10];
- int i = 1;
- for (AnyType item : items) {
- array[ i++] = item;
- }
- buildHeap();
- }
- /**
- * Insert into the priority queue, maintaining heap order. Duplicates are
- * allowed.
- *
- * @param x the item to insert.
- */
- //om mindre än parent perculate annars lägg till som child
- //lägg till children tills children= max nr av children i ett subträd
- public void insert(AnyType x) {
- if (currentSize == array.length - 1) {
- enlargeArray(array.length * children + 1);
- }
- // Percolate up
- int hole = ++currentSize;
- for (array[ 0] = x; hole > 1 && x.compareTo(array[ parentIndex(hole)]) < 0; hole = parentIndex(hole)) {
- array[ hole] = array[ parentIndex(hole)];
- }
- array[ hole] = x;
- }
- private void enlargeArray(int newSize) {
- AnyType[] old = array;
- array = (AnyType[]) new Comparable[newSize];
- for (int i = 0; i < old.length; i++) {
- array[ i] = old[ i];
- }
- }
- /**
- * Find the smallest item in the priority queue.
- *
- * @return the smallest item, or throw an UnderflowException if empty.
- */
- public AnyType findMin() {
- if (isEmpty()) {
- throw new UnderflowException();
- }
- return array[ 1];
- }
- /**
- * Remove the smallest item from the priority queue.
- *
- * @return the smallest item, or throw an UnderflowException if empty.
- */
- public AnyType deleteMin() {
- if (isEmpty()) {
- throw new UnderflowException();
- }
- AnyType minItem = findMin();
- array[1] = array[ currentSize];
- array[currentSize] = null;
- currentSize--;
- percolateDown(1);
- return minItem;
- }
- /**
- * Establish heap order property from an arbitrary arrangement of items.
- * Runs in linear time.
- */
- private void buildHeap() {
- for (int i = currentSize / 2; i > 0; i--) {
- percolateDown(i);
- }
- }
- /**
- * Test if the priority queue is logically empty.
- *
- * @return true if empty, false otherwise.
- */
- public int size() {
- return currentSize;
- }
- public boolean isEmpty() {
- return currentSize == 0;
- }
- /**
- * Make the priority queue logically empty.
- */
- public void makeEmpty() {
- currentSize = 0;
- }
- /**
- * Internal method to percolate down in the heap.
- *
- * @param hole the index at which the percolate begins.
- */
- private void percolateDown(int hole) {
- int child;
- AnyType tmp = array[ hole];
- for (; firstChildIndex(hole) <= currentSize; hole = child) {
- child = firstChildIndex(hole) + 1;
- int smallestChild = firstChildIndex(hole);
- int test = firstChildIndex(hole);
- for (int i = 0; i < children; i++) {
- System.out.println("i "+i);
- System.out.println("child index" + child + " and child value "+array[child]);
- System.out.println("array length "+array.length);
- if (array[child] != null) {
- if (array[child] != null && array[smallestChild].compareTo(array[ child]) < 0) {
- child++;
- } else {
- smallestChild = child;
- child++;
- }
- } else if((child+1)>=array.length) {
- break;
- } else {
- child++;
- }
- }
- child = smallestChild;
- if (array[child] != null && array[ child].compareTo(tmp) < 0) {
- array[ hole] = array[ child];
- } else {
- break;
- }
- }
- array[ hole] = tmp;
- }
- //generiska get-metoder för att hitta first child och parent
- public int firstChildIndex(int parent) {
- if (parent == 0) {
- throw new IllegalArgumentException();
- }
- return parent * children - (children - 2);
- //return 2 + (children *(parent-1));
- }
- public int parentIndex(int child) {
- if (child < 2) {
- throw new IllegalArgumentException();
- }
- //return (child - 2) / children + 1;
- //return (int)Math.floor((child-1)/children);
- //return (child + children - 1) / children;
- //int tal = (int)Math.ceil((child - 1.0) / children);
- //System.out.println("tal wo ceil "+tal);
- //tal =Math.ceil(tal);
- //System.out.println("tal w ceil "+tal);
- return (int) Math.ceil((child - 1.0) / children);
- }
- public AnyType get(int i) {
- return array[i];
- }
- // public AnyType getIndex(int i){
- // AnyType yeah = array[i];
- // return yeah;
- // }
- // Test program
- // public static void main( String [ ] args )
- // {
- // int numItems = 10000;
- // BinaryHeap<Integer> h = new BinaryHeap<>( );
- // int i = 37;
- //
- // for( i = 37; i != 0; i = ( i + 37 ) % numItems )
- // h.insert( i );
- // for( i = 1; i < numItems; i++ )
- // if( h.deleteMin( ) != i )
- // System.out.println( "Oops! " + i );
- // }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement