Thread: Binary Heap Help

Basically, I am creating a priority based cpu scheduling for my assignment.

This the outline of what I need to do:
1.The binary heap has a size of 101, and is implemented using an array and a heapSize index.
2. Each object in the heap is a process that contains the following data fields: (a) nice value (key), and (b) process ID (a sequence number).
3. The process objects in the heap are organized based upon their nice values, i.e. the nice value of a process must be no greater than that of its children.
4. A process is inserted into the heap using heap structure property and heap order property stated in step 3.
5. A process with the minimum nice values is removed from the heap using heap structure property and heap order property stated in step 3.

And in my driver this is what I need to do:
1. Create two instances of heap objects where the arrays are intially empty.
2. Create 100 processes in such a manner that their IDs sequentially go from 1 to 100, and their nice values are between 0 and 39 (use a random generator). Then put them sequentially into the array of the first heap.
3. Use "buildHeap" algorithm to reorganize the first heap according to the heap order property.
4. Print out the content of the 1st heap sequentially.
5. Perform "deleteMin" to remove a process from the first heap (then the process is running), then "insert" it into the second heap (the process returns to the waiting queue after running out of its time share).
6. Keep doing step 5 till the first heap becomes empty and the second full.
7. Print out the content of the 2nd heap sequentially.
8. Compare if the printouts of the two heaps are the same.

So, I got the driver part down and I got majority of the code I need to complete my assignment. However, I am having a hard time making the heap with objects. Here's what I got so far. You can ignore all the commented code, I was just testing things. I am only trying to insert the process into the heap first before I try to deleteMin and so on. And I am only testing it with 5 processes not 100. If I can get the insertion to work, then I can get the rest.

import java.util.*;

public class BinaryHeap
{
private static int heapSize;//Size of the heap
private static BinaryHeap array[];//Array of the heap
//private static int array[];
private static int processID;//Process ID number
private static int niceValue;//Nice value
private static BinaryHeap h1;//First heap
private static BinaryHeap h2;//Second heap

/*private BinaryHeap(int processID, int niceValue)
{
this.processID = processID;
this.niceValue = niceValue;
}*/

private BinaryHeap()
{
processID = 0;
niceValue = 0;
}

private BinaryHeap(int capacity)
{
heapSize = 0;
//array = new int[capacity + 1];
array = new BinaryHeap[capacity + 1];

for(int i = 0; i < array.length; i++)
{
array[i] = new BinaryHeap();
}
}

private void setProcessID(int processID)
{
this.processID = processID;
}

private void setNiceValue(int niceValue)
{
this.niceValue = niceValue;
}

private int getProcessID()
{
return processID;
}

private int getNiceValue()
{
return niceValue;
}

private boolean isFull()
{
return heapSize == array.length - 1;
}

private boolean isEmpty()
{
return heapSize == 0;
}

/*private void percolateDown(int hole)
{
int child;
int tmp = array[hole];
for( ; hole * 2 <= heapSize; hole = child)
{
child = hole * 2;
if(child != heapSize && array[child + 1] < array[child])
{
child++;
}
if(array[child] < tmp)
{
array[hole] = array[child];
}else
{
break;
}
}
array[hole] = tmp;
}*/

private void insert(int x, int y)
{
if(isFull())
{
throw new NoSuchElementException("Overflow");
}

/* Percolate up */
int hole = ++heapSize;
//System.out.println(array[hole/2].getNiceValue());
/*for( ; hole > 1 && x < array[hole/2]; hole /= 2)
{
array[hole] = array[hole/2];
}
array[hole] = x;*/

for( ; hole > 1 && y < array[hole/2].getNiceValue(); hole /= 2)
{
array[hole].setProcessID(array[hole/2].getProcessID());
array[hole].setNiceValue(array[hole/2].getNiceValue());
//System.out.println(array[hole].getProcessID() + " " + array[hole].getNiceValue() + " ");
}
array[hole].setProcessID(x);
array[hole].setNiceValue(y);
}

/*private int deleteMin()
{
if(isEmpty())
throw new NoSuchElementException("Overflow");
int minItem = array[1];
array[1] = array[heapSize--];
percolateDown(1);

return minItem;
}*/

/*private void buildHeap()
{
for(int i = heapSize/2; i > 0; i--)
{
percolateDown(i);
}
}*/

public static void main(String[] args)
{
int num1 = 0;
int num2 = 0;
h1 = new BinaryHeap(5);
//h2 = new BinaryHeap(10);
Random rand = new Random();

for(int i = 1; i < array.length; i++)
{
num1 = rand.nextInt(39);
for(int j = 1; j < array.length; j++)
{
System.out.print(array[i].getProcessID() + " " + array[i].getNiceValue() + " ");
}
System.out.println();
h1.insert(i, num1);
}

for(int i = 1; i < array.length; i++)
{
System.out.print(array[i].getProcessID() + " " + array[i].getNiceValue() + " ");
}
/*for(int i = 1; i < array.length; i++)
{
num1 = rand.nextInt(39);
h1.insert(num1);
}
h1.buildHeap();

for(int i = 1; i < array.length; i++)
{
System.out.print(array[i] + " ");
}
System.out.println();

int tmp[] = new int[heapSize + 1];
for(int i = 1; i < tmp.length; i++)
{
num2 = h1.deleteMin();
tmp[i] = num2;
}

h2 = new BinaryHeap(10);
for(int i = 1; i < array.length; i++)
{
h2.insert(tmp[i]);
}
h2.buildHeap();

for(int i = 1; i < array.length; i++)
{
System.out.print(array[i] + " ");
}
System.out.println();*/

}
}

So when I run my code, the array is initially empty. When it inserts a process into the array, the process is inserted into every index in the array. So for example, my array size is 5 and contained in it is 0 0, 0 0, 0 0, 0 0, 0 0 meaning the array is empty. When I insert a process like 1 7, the array now contains 1 7, 1 7, 1 7, 1 7, 1 7 and if a second process is inserted like 2 5, it will now be 2 5, 2 5, 2 5, 2 5, 2 5 and so on. But what I want is an array that follows the min heap order property, so it should turn out like this 0 0, 2 5, 1 7, ... and so on. I have been looking at my code for hours and I can't seem to figure out why it fills the indexes with the same processes. If someone can catch that error, that would be awesome and I can figure the rest out from there.