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 8 of 8

Thread: PriorityQ and MaxHeap

  1. #1
    Junior Member
    Join Date
    Nov 2011
    Posts
    11
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default PriorityQ and MaxHeap

    Okay, so I have an assign,ent to write a priority queue that implements a max heap. I've only just started the program and this is what I have for my MyMaxHeap class:

    public class MyMaxHeap{
      private static class jobAd{
        public float salary;
        public float dist;
        public float score;
     
        public jobAd(float s, float d){
          s = salary;
          d = dist;
          score = s + 3 * (30 - d);
        }
      }
     
      private jobAd[] theHeap;
      private int size;
      private int capacity;
     
      private static final int initial_cap = 5;
     
      public MyMaxHeap(){
        size = 0;
        capacity = initial_cap;
        theHeap = new jobAd[capacity];
      }
     
      public MyMaxHeap(jobAd[] arr, int n){
        theHeap = arr;
        n = size;
      }
     
      public int size(){
        return size;
      }
     
      public boolean add(jobAd job){
        if ((size >= capacity) || (job == null)){
          return false;
        }
        return true;
     
      }
     
     
      public static void main(String[] args){
        MyMaxHeap myHeap = new MyMaxHeap();
        System.out.println(myHeap.size());
      }
     
    }

    My problem here is that I don't understand how to add/insert a new new element to the list. I've tried a few things and they ended with several errors. Also, this heap is to be sorted by score. I don't know how to compare the two scores without using theHeap[index].score.compareTo(theHeap[index2] which also gives several errors. Please help!! I just need to know how to start this and then I'll work on it on my own. Thank you.


  2. #2
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: PriorityQ and MaxHeap

    Quote Originally Posted by lahegemon View Post
    Okay, so I have an assign,ent to write a priority queue that implements a max heap. I've only just started the program and this is what I have for my MyMaxHeap class:

    public class MyMaxHeap{
      private static class jobAd{
        public float salary;
        public float dist;
        public float score;
     
        public jobAd(float s, float d){
          s = salary;
          d = dist;
          score = s + 3 * (30 - d);
        }
      }
     
      private jobAd[] theHeap;
      private int size;
      private int capacity;
     
      private static final int initial_cap = 5;
     
      public MyMaxHeap(){
        size = 0;
        capacity = initial_cap;
        theHeap = new jobAd[capacity];
      }
     
      public MyMaxHeap(jobAd[] arr, int n){
        theHeap = arr;
        n = size;
      }
     
      public int size(){
        return size;
      }
     
      public boolean add(jobAd job){
        if ((size >= capacity) || (job == null)){
          return false;
        }
        return true;
     
      }
     
     
      public static void main(String[] args){
        MyMaxHeap myHeap = new MyMaxHeap();
        System.out.println(myHeap.size());
      }
     
    }

    My problem here is that I don't understand how to add/insert a new new element to the list. I've tried a few things and they ended with several errors. Also, this heap is to be sorted by score. I don't know how to compare the two scores without using theHeap[index].score.compareTo(theHeap[index2] which also gives several errors. Please help!! I just need to know how to start this and then I'll work on it on my own. Thank you.
    I've tried a few things and they ended with several errors.
    Such as.......?


    n = size;

    Don't you mean

    size = n;

    ?

    I don't see where size is set otherwise.

    What is the capacity value set to in

    public MyMaxHeap(jobAd[] arr, int n){
    theHeap = arr;
    n = size;
    }

    ?

    When is the jobAd array ever filled?
    Last edited by javapenguin; November 11th, 2011 at 06:31 PM.

  3. #3
    Think of me.... Mr.777's Avatar
    Join Date
    Mar 2011
    Location
    Pakistan
    Posts
    1,136
    My Mood
    Grumpy
    Thanks
    20
    Thanked 82 Times in 78 Posts
    Blog Entries
    1

    Default Re: PriorityQ and MaxHeap

    Do you understand the concept of Heap? If yes, start implementing and come back here after you get errors or you get stuck somewhere. You didn't even try anything except creating a self defined object. Naming an object heap will surely not make it working like a heap. You must take the concept of Heap, then think and start implementing.
    Regards

  4. #4
    Junior Member
    Join Date
    Nov 2011
    Posts
    11
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: PriorityQ and MaxHeap

    public class MyMaxHeap{
        private class jobAd{
        public float salary;
        public float dist;
        public float score;
     
        public jobAd(float s, float d){
          s = salary;
          d = dist;
          score = s + 3 * (30 - d);
        }
      }
     
      private jobAd[] theHeap;
      private int size;
      private int capacity;
     
      public MyMaxHeap(){
        size=0;
        capacity = 5;
        theHeap = new jobAd[capacity];
      }
     
      public MyMaxHeap(jobAd[] arr, int n){
        theHeap=arr;
        size=n;
        buildHeap();
      }
     
      public int getSize(){
        return size;
      }
     
      public boolean add(jobAd job){
        int index;
        if((size>=theHeap.length)||(job==null)){
          return false;
        }    
        theHeap[size++]=job;
        index=shiftUp(size-1);
        return true;
      }
     
      public jobAd removeMax(){
        if(size <= 0){
          return null;
        }
        swap(0,--size);
        shiftDown(0);
        return theHeap[size];
      }
     
      private void shiftDown(int index){
        int leftChild;
        if((index>=0)&&(index<(size/2))){
          leftChild=2*index+1;
          if(((leftChild+1)<size)&&((Comparable)theHeap[leftChild]).compareTo(theHeap[leftChild+1])<0){
            leftChild++;
          }
          if(((Comparable)theHeap[index]).compareTo(theHeap[leftChild])<0){
            swap(index,leftChild);
            shiftDown(leftChild);
          }
        }
      }
     
      private int shiftUp(int index){
        int parent;
        if((index>0)&&(index<size)){
          parent=(index-1)/2;
            if(((Comparable)theHeap[index]).compareTo(theHeap[parent])>0){
             swap(parent,index);
             return shiftUp(parent);
          }
        }
        return index;
      }
     
      private void swap(int i, int j)
      {
        if((i>=0)||(j>=0)||(i<theHeap.length)||(j<theHeap.length)){
        jobAd temp = theHeap[i];
        theHeap[i]=theHeap[j];
        theHeap[j]=temp;
        }
       }
     
      private void buildHeap()
      {
        int i;
        for(i=(size/2-1);i>=0;i--)
        {
          shiftDown(i);
        }
      }
     
        public void showList(){
        for(int i = 0; i < size; i++){
          System.out.println("List: " + theHeap[i]);
        }
      }
     
     
      public static void main(String[] args){
        MyMaxHeap myHeap = new MyMaxHeap();
        System.out.println(myHeap.size);
      }
    }

    Okay, so that's my code for my max heap so far, guys. It compiles without errors but notice that I have a jobAd class? I need my heap to be sorted by the value of score and I'm not sure if I'm doing that. I'd appreciate any help available thanks.

  5. #5
    Junior Member
    Join Date
    Nov 2011
    Posts
    11
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: PriorityQ and MaxHeap

    public class MyMaxHeap{
        private class jobAd{
        public float salary;
        public float dist;
        public float score;
     
        public jobAd(float s, float d){
          s = salary;
          d = dist;
          score = s + 3 * (30 - d);
        }
      }
     
      private jobAd[] theHeap;
      private int size;
      private int capacity;
     
      public MyMaxHeap(){
        size=0;
        capacity = 5;
        theHeap = new jobAd[capacity];
      }
     
      public MyMaxHeap(jobAd[] arr, int n){
        theHeap=arr;
        size=n;
        buildHeap();
      }
     
      public int getSize(){
        return size;
      }
     
      public boolean add(jobAd job){
        int index;
        if((size>=theHeap.length)||(job==null)){
          return false;
        }    
        theHeap[size++]=job;
        index=shiftUp(size-1);
        return true;
      }
     
      public jobAd removeMax(){
        if(size <= 0){
          return null;
        }
        swap(0,--size);
        shiftDown(0);
        return theHeap[size];
      }
     
      private void shiftDown(int index){
        int leftChild;
        if((index>=0)&&(index<(size/2))){
          leftChild=2*index+1;
          if(((leftChild+1)<size)&&((Comparable)theHeap[leftChild]).compareTo(theHeap[leftChild+1])<0){
            leftChild++;
          }
          if(((Comparable)theHeap[index]).compareTo(theHeap[leftChild])<0){
            swap(index,leftChild);
            shiftDown(leftChild);
          }
        }
      }
     
      private int shiftUp(int index){
        int parent;
        if((index>0)&&(index<size)){
          parent=(index-1)/2;
            if(((Comparable)theHeap[index]).compareTo(theHeap[parent])>0){
             swap(parent,index);
             return shiftUp(parent);
          }
        }
        return index;
      }
     
      private void swap(int i, int j)
      {
        if((i>=0)||(j>=0)||(i<theHeap.length)||(j<theHeap.length)){
        jobAd temp = theHeap[i];
        theHeap[i]=theHeap[j];
        theHeap[j]=temp;
        }
       }
     
      private void buildHeap()
      {
        int i;
        for(i=(size/2-1);i>=0;i--)
        {
          shiftDown(i);
        }
      }
     
        public void showList(){
        for(int i = 0; i < size; i++){
          System.out.println("List: " + theHeap[i]);
        }
      }
     
     
      public static void main(String[] args){
        MyMaxHeap myHeap = new MyMaxHeap();
        System.out.println(myHeap.size);
      }
    }

    Okay, that's my code. It compiles without error. However, I am confused about one thing and I was hoping you could clarify it for me. This is supposed to be a MaxHeap that sorts by score. How do I ensure that it is sorting by the value of score (in jobAd class) and not salary or dist (distance) ? Thanks!

  6. #6
    Junior Member
    Join Date
    Nov 2011
    Posts
    11
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: PriorityQ and MaxHeap

    capacity is set in a separate constructor also, look at my reply below. that's my current program but...well, my questions are in the same post. Thanks

  7. #7
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: PriorityQ and MaxHeap

    You manually define the comparison method. The way I prefer to do it is with a comparator object, but that may be too generic for what you're trying to accomplish here.

    It's probably fine for you to "hard code" what to compare in your MyMaxHeap class.

  8. The Following User Says Thank You to helloworld922 For This Useful Post:

    lahegemon (November 20th, 2011)

  9. #8
    Junior Member
    Join Date
    Nov 2011
    Posts
    11
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: PriorityQ and MaxHeap

    Precisely what I was thinking. Couldn't I just replace my comparisons for some of my theHeap[index] comparisons with theHeap[index].score comparisons? But then I would ave to write a separate function that returns score, right? Inside of my jobAd class? and Thanks for getting back to me so quickly.

Tags for this Thread