package datastructures; public class MinIntHeap implements IntHeap{ private int[] data; //contains the actual data private int size; //contains the size of the heap static final int DEFAULT_CAPACITY = 10; //the default capacity of a new heap //Creates a new empty heap of capacity at default size public MinIntHeap(){ this(DEFAULT_CAPACITY); } //Creates a new empty heap of specified capacity public MinIntHeap(int capacity){ data = new int[capacity]; size = 0; } //takes an array and makes it the data in the heap //O(nlogn) - there is a O(n) way to do it public MinIntHeap(int[] a){ //easy way below /*data = new int[a.length]; for(int i : a){ push(i); }*/ //trickier but better way data = a; size = a.length; for(int i = size/2-1; i > 0; i--){ int index = i; while(!checkHeapProperty(index)){ index = swapWithChild(index); } } //this looks like nlogn - but that isn't a tight bound //if we visualize the data and operations, we see that we're never actually going to exceed n } //creates a new heap merging the data from two heaps //O(nlogn) - there is a O(n) way to do it public MinIntHeap(MinIntHeap a, MinIntHeap b){ //easy way below data = new int[a.size()+b.size()]; /*addAll(a); addAll(b);*/ for(int i = 0; i < a.size(); i++){ data[i] = a.data[i]; } for(int i = 0; i < b.size(); i++){ data[i+a.size()] = b.data[i]; } size = a.size()+b.size(); for(int i = size/2-1; i > 0; i--){ int index = i; while(!checkHeapProperty(index)){ index = swapWithChild(index); } } } //Returns the top element of the heap //Throws an exception if the heap is empty //O(1) - 2+1 = 3 operations public int peek(){ if(isEmpty()){ throw new NoSuchElementException(); } return data[0]; } //Returns the size of the heap //O(1) - 1 operation public int size(){ return size; } //Returns true if the heap is empty //O(1) - 2 operations public boolean isEmpty(){ return size == 0; } //Adds a new element to the heap, maintaining the heap property //O(?) //Best case: O(1) if heap property is satisfied //Worst case: amortized O(log(n)), true is O(n) because of addCapacity() //Why log(n) - if n == 1, we do 1, if n == 9, we do 4, if n == 16 or 17 or 18..., we do 5 //In fact, this is based on powers of 2. First row has 2^0, second has 2^1, third has 2^2, fourth has 2^3 //First index of each row is number of elements in the row-1 //reverse exponential, log(n) - note that log(n) is better than n public void push(int element){ if(size > data.length){ addCapacity(); } data[size] = element; //Now we need to check the heap property - parent must always be smaller than the child int index = size++; int parent = parentIndex(index); while(!checkHeapProperty(index, parent)){ swapWithParent(index, parent); index = parent; parent = parentIndex(index); } } //Removes the top element from the heap, maintaining the heap property //O(?) //O(1) - 1 vote //O(N) - 0 votes //O(N^2) - 0 votes //O(log(n)) - 12 votes //O(2^N) - 0 votes //lost - 2 votes //several abstentions //related to depth of tree = O(log(n)) public int pop(){ if(size == 0){ throw new NoSuchElementException(); } int value = data[0]; data[0] = data[--size]; int index = 0; while(!checkHeapProperty(index)){ index = swapWithChild(index); } return value; } //Removes the top element of the heap, adds a new value, and then maintains the heap property. //O(log(n)) public int replace(int element){ if(size == 0){ throw new NoSuchElementException(); } int value = data[0]; data[0] = element; int index = 0; while(!checkHeapProperty(index)){ index = swapWithChild(index); } return value; } //Adds all elements from an IntHeap into the heap //This method is destructive - it empties h //This is a side effect and is usually bad - we want to avoid this normally //O(nlogn) public void addAll(IntHeap h){ while(!h.isEmpty()){ push(h.pop()); } } //returns the index of the parent of a node //O(1) private int parentIndex(int index){ return (index-1)/2; } //Return true if the heap property is maintained by child at index index, false if violated private boolean checkHeapProperty(int index, int parent){ if(index == 0){ return true; } //int parent = index - 1; //if(parent % 2 == 1){ // parent -= 1; //} //parent = parent/2; return data[parent]<=data[index]; } //Return true if the heap property is maintained by parent at index and children, false if violated private boolean checkHeapProperty(int index){ int child1 = 2*index + 1 int child2 = 2*index + 2 if(child1 >= size){ return true; }else if(child2 >= size){ return data[child1] >= data[index]; }else{ return data[child1] >= data[index] && data[child2] >= data[index]; //We use && because both children must be greater for the property to be satisfied } } //swaps parent and child values private void swapWithParent(int index, int parent){ int temp = data[parent]; data[parent] = data[index]; data[index] = temp; } //swaps parent with smallest child private int swapWithChild(int index){ int child1 = 2*index + 1 int child2 = 2*index + 2 int target = child2; if(child1 >= size){ return 0; // this should not happen }else if(child2 >= size || data[child1] < data[child2]){ target = child1; } int temp = data[target]; data[target] = data[index]; data[index] = temp; return target; } //Extends the array if it is full private void addCapacity(){ int[] temp = new int[data.length*2]; for(int i = 0; i < data.length; i++){ temp[i] = data[i]; } data = temp; } }
PLEASE DO THE METHODS AND INSTRUCTIONS
