Question

java binary heap operation counts

/*
* Add operation counts to all methods - 4pts
* No other methods/variables should be added/modified
*/
public class A6BH <E extends Comparable<? super E>> {
   private int defaultSize = 4;
   private int count = 0;
   private E[] heap;
   private int opCount = 0;
  
   public int getOpCount()
   {
       return opCount;
   }
   public void resetOpCount()
   {
       opCount = 0;
   }

   public A6BH()
   {
       heap = (E[])new Comparable[defaultSize];
   }
   public A6BH(int size)
   {
       heap = (E[])new Comparable[this.nextSize(size)];
   }
   public A6BH(E[] items)
   {
       heap = (E[])new Comparable[this.nextSize(items.length)];
       this.addAll(items);
   }

   public void addAll(E[] items)
   {
       //make sure there is room for all new items
       if(count+items.length >= heap.length)
       {
           growArray(this.nextSize(count+items.length));
       }

       for(E item : items)//copy new items in order
       {
           count++;
           heap[count] = item;
       }

       this.buildHeap();//fix heap order
   }
   private void buildHeap()
   {
       for(int i = count >> 1; i > 0; i--)
       {
           percolateDown(i);
       }
   }

   public void insert(E val)
   {
       //make sure we have room for new item
       if(count+1 >= heap.length)
       {
           growArray();
       }
       count++;
       heap[0] = val;//temporary storage
       percolateUp(count);
   }
   private void percolateUp(int pos)
   {
       //pos>>1 = pos/2 - getting to parent of empty space
       for(;heap[pos>>1].compareTo(heap[0]) > 0;pos = pos>>1)
       {
           heap[pos] = heap[pos>>1];//move parent down a level
       }
       heap[pos] = heap[0];//take value from initial insert and put in correct pos
   }

   public E findMin()
   {
       return (count > 0)?heap[1]:null;
   }
   public E deleteMin()
   {
       if(count > 0)
       {
           E temp = heap[1];

           heap[1] = heap[count];//moved last value to top
           count--;//decrease size
           percolateDown(1);//move top value down to final position

           return temp;
       }
       else
       {
           return null;//no items in heap
       }
   }
   private void percolateDown(int pos)
   {
       int firstChild = pos << 1;//pos * 2
       E temp = heap[pos];
       for(;pos<<1 <= count; pos = firstChild, firstChild = pos<<1)
       {
           if(firstChild+1 <= count)//there is a second child
           {
               if(heap[firstChild].compareTo(heap[firstChild+1]) > 0)
               {
                   firstChild++;
               }
           }
           //firstChild is now the index of the smaller child
           if(temp.compareTo(heap[firstChild]) > 0)
           {
               heap[pos] = heap[firstChild];//move child up to parent and continue
           }
           else
           {
               break;//stop loop because we found correct position for temp
           }
       }
       heap[pos] = temp;
   }

   public String toString()
   {
       String output = "Heap Size:"+heap.length+"\n";
       for(int i = 1; i <= count; i++)
       {
           output += heap[i]+",";
       }
       return output;
   }

   public boolean isEmpty()
   {
       return count == 0;
   }
   public void makeEmpty()
   {
       count = 0;
   }

   private void growArray()//O(N)
   {
       growArray(heap.length << 1);//heap.length * 2
   }
   private void growArray(int size)
   {
       //new array that is twice as big
       E[] newArr = (E[])new Comparable[size];
       //Move values to new array
       for(int i = 1; i <= count; i++)//O(N)
       {
           newArr[i] = heap[i];
       }
       //System.out.println(Arrays.toString(newArr));
       heap = newArr;//replace small array with new one
   }
   private int nextSize(int size)
   {
       return 1 << (Integer.toBinaryString(size).length() + 1);//2^(number of bits to represent number)
   }
}

======================================================================================================

import java.util.Arrays;
import java.util.Random;

public class A6Driver {

   public static void main(String[] args) {
       Random randGen = new Random();
       randGen.nextInt(10);//better timing values
       long time = System.nanoTime();//better timing values
       A6BH<Integer> heap = new A6BH<>();
       heap.insert(5);//better timing values
       int testCases = 7;
       for(int i = 1; i <= testCases; i++)
       {
           System.out.println("Test "+i);
           int N = (int)Math.pow(10, i);
           Integer[] randoms = new Integer[N];
           time = System.nanoTime();
           for(int j = 0; j < randoms.length; j++)
           {
               randoms[j] = randGen.nextInt(N)+1;
           }
           time = System.nanoTime() - time;
           System.out.println("Generate "+N+" Randoms: "+(time/1000000000.0)+ " seconds");
           time = System.nanoTime();
           heap = new A6BH<>(randoms);
           time = System.nanoTime() - time;
           System.out.println("Bulk insert: " + (time/1000000000.0)+" seconds");
           System.out.println("Bulk insert: " + heap.getOpCount()+" operations");
           time = System.nanoTime();
           heap = new A6BH<>();
           for(int j = 0; j < randoms.length; j++)
           {
               heap.insert(randoms[j]);
           }
           time = System.nanoTime() - time;
           System.out.println("Individual insert: " + (time/1000000000.0)+" seconds");
           System.out.println("Individual insert: " + heap.getOpCount()+" operations");
           System.out.println();
       }
   }

}

Answer 1

/******************************A6BH.java*****************************/

/*
* Add operation counts to all methods - 4pts
* No other methods/variables should be added/modified
*/
public class A6BH<E extends Comparable<? super E>> {
   private int defaultSize = 4;
   private int count = 0;
   private E[] heap;
   private int opCount = 0;

   public int getOpCount() {
       return opCount;
   }

   public void resetOpCount() {
       opCount = 0;
   }

   public A6BH() {
       heap = (E[]) new Comparable[defaultSize];
       opCount++;
   }

   public A6BH(int size) {
       heap = (E[]) new Comparable[this.nextSize(size)];
       opCount++;
   }

   public A6BH(E[] items) {
       heap = (E[]) new Comparable[this.nextSize(items.length)];
       this.addAll(items);
       opCount++;
   }

   public void addAll(E[] items) {
       // make sure there is room for all new items
       if (count + items.length >= heap.length) {
           growArray(this.nextSize(count + items.length));
       }

       for (E item : items)// copy new items in order
       {
           count++;
           heap[count] = item;
       }
      
       this.buildHeap();// fix heap order
       opCount++;
   }

   private void buildHeap() {
       for (int i = count >> 1; i > 0; i--) {
           percolateDown(i);
       }
       opCount++;
   }

   public void insert(E val) {
       // make sure we have room for new item
       if (count + 1 >= heap.length) {
           growArray();
       }
       count++;
       heap[0] = val;// temporary storage
       percolateUp(count);
       opCount++;
   }

   private void percolateUp(int pos) {
       // pos>>1 = pos/2 - getting to parent of empty space
       for (; heap[pos >> 1].compareTo(heap[0]) > 0; pos = pos >> 1) {
           heap[pos] = heap[pos >> 1];// move parent down a level
       }
       heap[pos] = heap[0];// take value from initial insert and put in correct pos
       opCount++;
   }

   public E findMin() {
       opCount++;
       return (count > 0) ? heap[1] : null;
      
   }

   public E deleteMin() {
       opCount++;
       if (count > 0) {
           E temp = heap[1];

           heap[1] = heap[count];// moved last value to top
           count--;// decrease size
           percolateDown(1);// move top value down to final position

           return temp;
       } else {
           return null;// no items in heap
       }
   }

   private void percolateDown(int pos) {
       opCount++;
       int firstChild = pos << 1;// pos * 2
       E temp = heap[pos];
       for (; pos << 1 <= count; pos = firstChild, firstChild = pos << 1) {
           if (firstChild + 1 <= count)// there is a second child
           {
               if (heap[firstChild].compareTo(heap[firstChild + 1]) > 0) {
                   firstChild++;
               }
           }
           // firstChild is now the index of the smaller child
           if (temp.compareTo(heap[firstChild]) > 0) {
               heap[pos] = heap[firstChild];// move child up to parent and continue
           } else {
               break;// stop loop because we found correct position for temp
           }
       }
       heap[pos] = temp;
   }

   public String toString() {
       String output = "Heap Size:" + heap.length + "\n";
       for (int i = 1; i <= count; i++) {
           output += heap[i] + ",";
       }
       opCount++;
       return output;
   }

   public boolean isEmpty() {
       opCount++;
       return count == 0;
      
   }

   public void makeEmpty() {
       opCount++;
       count = 0;
   }

   private void growArray()// O(N)
   {
       opCount++;
       growArray(heap.length << 1);// heap.length * 2
   }

   private void growArray(int size) {
       opCount++;
       // new array that is twice as big
       E[] newArr = (E[]) new Comparable[size];
       // Move values to new array
       for (int i = 1; i <= count; i++)// O(N)
       {
           newArr[i] = heap[i];
       }
       // System.out.println(Arrays.toString(newArr));
       heap = newArr;// replace small array with new one
   }

   private int nextSize(int size) {
       opCount++;
       return 1 << (Integer.toBinaryString(size).length() + 1);// 2^(number of bits to represent number)
   }
}

/**********************************A6Driver.java*************************/

import java.util.Random;

public class A6Driver {

   public static void main(String[] args) {
       Random randGen = new Random();
       randGen.nextInt(10);// better timing values
       long time = System.nanoTime();// better timing values
       A6BH<Integer> heap = new A6BH<>();
       heap.insert(5);// better timing values
       int testCases = 7;
       for (int i = 1; i <= testCases; i++) {
           System.out.println("Test " + i);
           int N = (int) Math.pow(10, i);
           Integer[] randoms = new Integer[N];
           time = System.nanoTime();
           for (int j = 0; j < randoms.length; j++) {
               randoms[j] = randGen.nextInt(N) + 1;
           }
           time = System.nanoTime() - time;
           System.out.println("Generate " + N + " Randoms: " + (time / 1000000000.0) + " seconds");
           time = System.nanoTime();
           heap = new A6BH<>(randoms);
           time = System.nanoTime() - time;
           System.out.println("Bulk insert: " + (time / 1000000000.0) + " seconds");
           System.out.println("Bulk insert: " + heap.getOpCount() + " operations");
           time = System.nanoTime();
           heap = new A6BH<>();
           for (int j = 0; j < randoms.length; j++) {
               heap.insert(randoms[j]);
           }
           time = System.nanoTime() - time;
           System.out.println("Individual insert: " + (time / 1000000000.0) + " seconds");
           System.out.println("Individual insert: " + heap.getOpCount() + " operations");
           System.out.println();
       }
   }

}
/******************output***********************/

Test 1
Generate 10 Randoms: 3.8E-6 seconds
Bulk insert: 2.22E-5 seconds
Bulk insert: 9 operations
Individual insert: 8.0E-6 seconds
Individual insert: 25 operations

Test 2
Generate 100 Randoms: 1.91E-5 seconds
Bulk insert: 2.31E-5 seconds
Bulk insert: 54 operations
Individual insert: 3.36E-5 seconds
Individual insert: 211 operations

Test 3
Generate 1000 Randoms: 2.665E-4 seconds
Bulk insert: 1.593E-4 seconds
Bulk insert: 504 operations
Individual insert: 1.757E-4 seconds
Individual insert: 2017 operations

Test 4
Generate 10000 Randoms: 9.146E-4 seconds
Bulk insert: 5.704E-4 seconds
Bulk insert: 5004 operations
Individual insert: 7.722E-4 seconds
Individual insert: 20025 operations

Test 5
Generate 100000 Randoms: 0.0041557 seconds
Bulk insert: 0.0042989 seconds
Bulk insert: 50004 operations
Individual insert: 0.0050859 seconds
Individual insert: 200031 operations

Test 6
Generate 1000000 Randoms: 0.0167059 seconds
Bulk insert: 0.0415155 seconds
Bulk insert: 500004 operations
Individual insert: 0.0200221 seconds
Individual insert: 2000037 operations

Test 7
Generate 10000000 Randoms: 4.2170673 seconds
Bulk insert: 0.2282556 seconds
Bulk insert: 5000004 operations
Individual insert: 0.3075255 seconds
Individual insert: 20000045 operations

Please let me know if you have any doubt or modify the answer, Thanks :)