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

Thread: MaxHeap/ PriorityQ HELP PLEASE!

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

    Exclamation MaxHeap/ PriorityQ HELP PLEASE!

    public class MyPriorityQueue{
      private static class jobAd{
        public float salary;
        public float dist;
        public float score;
     
        public jobAd(){
        }
     
        public jobAd(float s, float d){
          salary = s;
          dist = d;
          score = s + 3 * (30 - d);
        }
      }
     
      public class MyMaxHeap{
      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;
        size = n;
        buildHeap();
      }
     
      public int lc(int index){
        return (2*index) + 1;
      }
     
      public int rc(int index){
        return (2*index) + 2;
      }
     
      public int parent(int index){
        if (index % 2 == 0) {
          return (index - 2)/2;
        }
        else{
          return (index - 1)/2;
        }
      }
     
      public int size(){
        return size;
      }
     
      public int compare(int i, int j){
        if(theHeap[i].score > theHeap[j].score){
          return 1;
        }
        if(theHeap[i].score == theHeap[j].score){
          return 0;
        }
        else{
          return -1;
        }
      }
     
      public boolean add(jobAd job){
        if(size == capacity){
          jobAd[] newJobAd = new jobAd[2 * size];
          System.arraycopy(newJobAd,0,theHeap,0,capacity);
          theHeap = newJobAd;
        }
          theHeap[size] = job;
          size++;
          if(size > 1){
            shiftDown(parent(size - 1));
        }
          return true;
      }
     
      private boolean rectify(int index){
        if(lc(index) < size){
          // if there is no right child or the left child is greater than the right child
          if(rc(index) >= size || compare(lc(index), rc(index)) > 0){
            // if the left child is greater than the index
            if(compare(lc(index), index) > 0){
              swap(lc(index), index); 
              return true;
            }
          }
          // if the right child is greater than index
          else if(compare(rc(index), index) > 0){
            swap(rc(index), index);
            return true;
          }
        }
        return false;
      }
     
     public jobAd removeMax(){
        theHeap[0] = theHeap[--size];
        for(int i = 0; i < size - 1; i++){
          rectify(i);
        }
        return theHeap[0];
      }         
     
      public void buildHeap(){
        int temp = size;
        size = 0;
        for(int i = 0; i < temp; i++){
          add(theHeap[i]);
        }
      }
     
      public void shiftDown(int index){
        if(rectify(index) && index != 0){
          shiftDown(parent(index));
        }
      }
     
      public void shiftUp(int index){
        if(index >= 0 && index < size){
          if(compare(index, parent(index)) > 0){
            swap(parent(index), index);
            shiftUp(parent(index));
        }
      }
      }
     
      public void swap(int i, int j){
        jobAd temp = new jobAd();
        temp = theHeap[i];
        theHeap[i] = theHeap[j];
        theHeap[i] = temp;
      }
     
      public void showList(){
        int i;
        for(i = 0; i < size; i++){
          System.out.println("List: " + theHeap[i].score);
        }
      }
     
     /* 
      public static void main(String[] args){
        MyMaxHeap myQ = new MyMaxHeap();
        jobAd job1 = new jobAd((float) 1.1, (float) 13.01);
        myQ.add(job1);
        jobAd job2 = new jobAd((float) 2.1, (float) 13.01);
        myQ.add(job2);
        jobAd job3 = new jobAd((float) 3.1, (float) 13.01);
        myQ.add(job3);
        jobAd job4 = new jobAd((float) 4.1, (float) 13.01);
        myQ.add(job4);
        jobAd job5 = new jobAd((float) 5.1, (float) 13.01);
        myQ.add(job5);
        myQ.showList();
        //s + 3 * (30 - d)
        System.out.println(myQ.size());
        }*/
     
    }
     
      private MyMaxHeap theQueue;
      private int size;
     
      public MyPriorityQueue(){
        theQueue = new MyMaxHeap();
      }
     
      public MyPriorityQueue(jobAd[] arr, int n){
        theQueue = new MyMaxHeap(arr, n);
      }
     
      public int size(){
        return size;
      }
     
      public boolean isEmpty(){
        if(theQueue == null){
          return true;
        }
        return false;
      }
     
      public boolean offer(jobAd jA){
        theQueue.add(jA);
        return true;
      }
     
      public jobAd remove(){
        if(isEmpty()){
          return null;
        }
        else{
        theQueue.removeMax();
        return theQueue.removeMax();
        }
      }
     
      public jobAd peek(){
        if(isEmpty()){
          return null;
        }
        else{
          return theQueue[0]; //return queue item at index 0, which is the max
        }
      }
     
      public void showList(){
        int i;
        for(i = 0; i < size; i++){
          System.out.println("List: " + theQueue[i]); //print out element at index i, which increments to print out rest of list
        }
      }
     
      public static void main(String[] args){
        MyPriorityQueue myQ = new MyPriorityQueue();
        jobAd job1 = new jobAd((float) 1.1, (float) 13.01);
        myQ.offer(job1);
        jobAd job2 = new jobAd((float) 2.1, (float) 13.01);
        myQ.offer(job2);
        jobAd job3 = new jobAd((float) 3.1, (float) 13.01);
        myQ.offer(job3);
        jobAd job4 = new jobAd((float) 4.1, (float) 13.01);
        myQ.offer(job4);
        jobAd job5 = new jobAd((float) 5.1, (float) 13.01);
        myQ.offer(job5);
        myQ.showList();
        //s + 3 * (30 - d)
        System.out.println(myQ.size());
        }
     
    }

    That's my code right now and I get these errors:

    2 errors found:
    File: C:\Users\Class2014\Desktop\MyPriorityQueue.java [line: 209]
    Error: C:\Users\Class2014\Desktop\MyPriorityQueue.java:20 9: array required, but MyPriorityQueue.MyMaxHeap found
    File: C:\Users\Class2014\Desktop\MyPriorityQueue.java [line: 216]
    Error: C:\Users\Class2014\Desktop\MyPriorityQueue.java:21 6: array required, but MyPriorityQueue.MyMaxHeap found


  2. #2
    Grand Poobah
    Join Date
    Mar 2011
    Posts
    1,545
    My Mood
    Grumpy
    Thanks
    0
    Thanked 167 Times in 158 Posts

    Default Re: MaxHeap/ PriorityQ HELP PLEASE!

    Did you read the error messages?
    Did you try to understand them?

    They are quite straight forward. On lines 209 and 216 you are attempting to use a MyMaxHeap object instead of an array.
    Improving the world one idiot at a time!

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

    Default Re: MaxHeap/ PriorityQ HELP PLEASE!

    See I understand that part but what I don't understand is how to call theQueue at an index...would I be using

    return theQueue(arr, 0);

    or something? That's what I don't understand. Thanks!

Similar Threads

  1. PriorityQ and MaxHeap
    By lahegemon in forum What's Wrong With My Code?
    Replies: 7
    Last Post: November 20th, 2011, 06:01 PM

Tags for this Thread