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: Implementing a priority queue using a max heap

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

    Default Implementing a priority queue using a max heap

    Hi, I've been working on implementing a priority queue using a max heap and have managed to create a max heap that works however when I try to implement it with the priority queue it doesn't work. I'm not sure if I'm implementing right. Right now I have the two classes in two seperate files.

    public class MyMaxHeap{
     
      private Object[] theHeap;
      private int size;
     
      public MyMaxHeap(){
        size=0;
        theHeap = new Object[0];
      }
     
      public MyMaxHeap(int cap)
      {
        size=0;
        theHeap = new Object[cap];
      }
     
      public MyMaxHeap(Object[] arr, int n)
      {
        theHeap=arr;
        size=n;
        buildHeap();
      }
     
      public int getSize()
      {
        return size;
      }
     
      public boolean add(Object o)
      {
        int index;
        if((size>=theHeap.length)||(o==null))
        {
          return false;
        }    
        theHeap[size++]=o;
        index=shiftUp(size-1);
        return true;
      }
     
      public Object removeMax()
      {
        if(size <= 0)
        {
          return null;
        }
        swap(0,--size);
        shiftDown(0);
        return theHeap[size];
      }
     
      private void shiftDown(int index)
      {
        int lc;
        if((index>=0)&&(index<(size/2)))
        {
          lc=2*index+1;
          if(((lc+1)<size)&&((Comparable)theHeap[lc]).compareTo(theHeap[lc+1])<0)
          {
            lc++;
          }
          if(((Comparable)theHeap[index]).compareTo(theHeap[lc])<0)
          {
            swap(index,lc);
            shiftDown(lc);
          }
        }
      }
     
      private int shiftUp(int index)
      {
        int p;
        if((index>0)&&(index<size)){
          p=(index-1)/2;
            if(((Comparable)theHeap[index]).compareTo(theHeap[p])>0){
             swap(p,index);
             return shiftUp(p);
          }
        }
        return index;
      }
     
      private void swap(int x, int y)
      {
        if((x>=0)||(y>=0)||(x<theHeap.length)||(y<theHeap.length)){
        Object temp = theHeap[x];
        theHeap[x]=theHeap[y];
        theHeap[y]=temp;
        }
       }
     
      private void buildHeap()
      {
        int i;
        for(i=(size/2-1);i>=0;i--)
        {
          shiftDown(i);
        }
      }
     
      public void parse()
      {
        int i;
        if(size>0){
        String ret= " ";
        for(i=0;i<size;i++){
          ret+= theHeap[i].toString() + " ";
          System.out.println(ret);
        }
        }
      }
     
     
     
     
    public static void main(String[] args){
     
    MyMaxHeap heap = new MyMaxHeap(10);
     heap.add(null);
     heap.add(47);
     heap.add(48);
     heap.add(49);
     heap.add(105);
     heap.add(77);
     heap.add(100);
     heap.add(10000);
     heap.add(50);
     heap.add(-10);
     heap.add(-5000);
     heap.add(null);
     heap.add(400);
     heap.removeMax();
     heap.removeMax();
     heap.removeMax();
     heap.removeMax();
     heap.parse();
     
     
     System.out.println(heap.getSize());
    }
    }

    public class MyPriorityQueue extends MyMaxHeap{
     
        private MyMaxHeap theQueue = new MyMaxHeap();
        private Object[] Q;
     
        public MyPriorityQueue(){
     
          theQueue = new MyMaxHeap();
     
        } 
     
    public MyPriorityQueue(Object arr[], int n){
     
         theQueue= new MyMaxHeap(arr,n);      
      }
     
     
       public boolean enqueue(Object o){
         if((o==null)||(getSize()<0)){
           return false;
         }
         System.out.println("j");
         System.out.println(theQueue.add(o));
         return theQueue.add(o);
     
        }
     
       public Object dequeue(){
     
         if(theQueue==null){
           return null;
         }
         theQueue.removeMax();
         System.out.println(theQueue.removeMax());
         return theQueue.removeMax();
      }
     
       public Object peek(){
     
         if(theQueue==null){
           return null;
         }
         return theQueue.removeMax();
       }
     
       public static void main(String[] args){
     
     
     
     
     
       }
    }
    Last edited by helloworld922; April 15th, 2011 at 02:07 AM.


  2. #2
    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: Implementing a priority queue using a max heap

    I don't see the point of having a MyPriorityQueue class if you already have a heap class, and I would especially caution against putting a MyMaxHeap as a field of a priority queue which extends MyMaxHeap.

    A priority queue is simply a method of traversal where the item with the highest priority (aka value) gets pulled. So if you're max heap class works correctly, all you need to do is pull the root item and you have the highest priority item on the priority queue.

    MyMaxHeap priorityQueue = new MyMaxHeap(); // no need for a separate class at all, a Priority queue was implemented directly in MyMaxHeap

    A few other things which look concerning:
    1. You have an object array as the underlying storage container for your heap class. In general objects are not comparable, especially between different objects (how do you compare a String to a JButton or an ArrayList?). I would strongly recommend creating a heap node class which would contain the data, as well as the "value" of that item on the heap.

    public class HeapNode
    {
        public Object data; // kind of bad practice, but oh well
        public int value; // use this value in your heap logic, your heap logic shouldn't do any comparisons/checks on data, only on value.
    }

    Your underlying heap data would then be an array of HeapNodes.

  3. #3
    Forum old-timer
    Join Date
    Nov 2008
    Location
    Faversham, Kent, UK
    Posts
    471
    My Mood
    Mellow
    Thanks
    4
    Thanked 58 Times in 54 Posts

    Default Re: Implementing a priority queue using a max heap

    Cross-posted on CodeGuru.

Similar Threads

  1. Priority Queue using comparable
    By jkalm in forum Collections and Generics
    Replies: 6
    Last Post: December 5th, 2010, 09:02 PM
  2. Implementing a queue or stack using a heap
    By tla280 in forum Java Theory & Questions
    Replies: 1
    Last Post: November 30th, 2010, 11:29 PM
  3. Replies: 4
    Last Post: July 21st, 2010, 04:07 PM
  4. Implementing a 5-heap with an array
    By TBBucs in forum Algorithms & Recursion
    Replies: 0
    Last Post: April 12th, 2010, 10:56 PM