Implementation of priority queue and max heap
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2

Thread: Implementation of priority queue and max heap

  1. #1
    Join Date
    Apr 2011
    Posts
    1

    Implementation of priority queue and 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){





    }
    }

  2. #2
    dlorde is offline Elite Member Power Poster
    Join Date
    Aug 1999
    Location
    UK
    Posts
    10,163

    Re: Implementation of priority queue and max heap

    Please post code inside CODE tags (see my sig) so it remains readable.

    E.T.A. Ah, don't bother - I see you've cross-posted on Java Programming Forums. I'm out.


    Programs must be written for people to read, and only incidentally for machines to execute...
    H. Abelson and G. Sussman
    Last edited by dlorde; April 15th, 2011 at 12:54 PM.
    Please use &#91;CODE]...your code here...&#91;/CODE] tags when posting code. If you get an error, please post the full error message and stack trace, if present.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center