Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: Binary Heap Help

  1. #1
    Junior Member
    Join Date
    Apr 2014
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Binary Heap Help

    Please edit your post and wrap your code with code tags:
    [code=java]
    YOUR CODE HERE
    [/code]
    to get highlighting and preserve formatting.
    If you don't understand my answer, don't ignore it, ask a question.

Similar Threads

  1. Replies: 7
    Last Post: January 23rd, 2013, 09:04 PM
  2. heap size vs heap used
    By aueddonline in forum Java Theory & Questions
    Replies: 5
    Last Post: February 10th, 2012, 01:59 PM
  3. binary heap
    By dabdi in forum Collections and Generics
    Replies: 0
    Last Post: November 16th, 2011, 05:43 PM
  4. Binary datafile and object creation according to binary tag ?
    By loicus in forum Object Oriented Programming
    Replies: 4
    Last Post: October 14th, 2011, 01:00 PM
  5. heap ordering using binary tree
    By student in forum Java Theory & Questions
    Replies: 5
    Last Post: October 27th, 2010, 05:25 PM