Priority Queue

This is a discussion on Priority Queue within the C++ Programming forums, part of the General Programming Boards category; I am trying to implement a priority queue using a doubly-linked list, but am having trouble with percolating the nodes ...

  1. #1
    Registered User
    Join Date
    Mar 2004
    Posts
    5

    Priority Queue

    I am trying to implement a priority queue using a doubly-linked list, but am having trouble with percolating the nodes up the list. Whenever a node travels more than two levels up, it leaves either a copy of itself or another node in that thread where it should be the node it replaced. The problem is that whenever I percolate, the address for the data is stored locally and not updated correctly. Here is some of my code in case that would help. The deletion of the keys is just something I did as a test, so they can more or less be ignored.


    Code:
    class PQueue2 {
    friend class dList<Queue2>;
        public:
            PQueue2();
            ~PQueue2();
            void insert(int key, Jval val);
            int minkey();
            Jval minval();
            void deletemin();
            int size();
            bool empty();
            void print_it();
            void moveto(int place);
            //  void dList<Queue2 *>::swap(Queue2 *, Queue2 *);
        protected:
            Queue2 *data;
             dList<Queue2 *> *Qlist;
             int Qsize;
    };
    ...
    void PQueue2::insert(int key, Jval val) {
        dList<Queue2 *> *temp;
        Queue2 *newdata, *olddata;
        int i, position, prev, current_key, newkey, newval;
    
        i = 0;
        newdata = new Queue2;
        olddata = new Queue2;
        olddata->key = key;
        olddata->val = val;
        temp = new dList<Queue2 *>();
    
        printf("  inside insert\n");
    
        if(Qsize++ == 0) { // Therefore, the list is empty
            Qlist->append(olddata);
            Qlist->first();
        }
    
        else { // Element(s) is/are present in the queue, so have to find insertion point
    
            position = Qsize;
            current_key = key;
            Qlist->append(olddata); // Inserts at end of list
    
            while(position > 1) {
                prev = position;
            position /= 2;
           
            moveto(position); // Moves to the last node's parent
    
            if(current_key < Qlist->get()->key){  // Swap with the parent node, which is the current one
    
                delete olddata;
                olddata = new Queue2;
                delete newdata;
                newdata = new Queue2;
                olddata->key = key;
                olddata->val = val;
                newdata->key = Qlist->get()->key;   // This is the data
                newdata->val.i = Qlist->get()->val.i; // To be moved
                moveto(prev); // Moves to the pointer which is to be moved up
            Qlist->deleteNode();
            Qlist->insertBeforeCursor(newdata);
    
            moveto(position);
    
            Qlist->deleteNode();
            Qlist->insertBeforeCursor(olddata);
                current_key = Qlist->get()->key;
            } // END of IF key < ...
        
            } // END WHILE
        } // END ELSE
    
    
        printf("  inside insert, the current tree is\n");
        dl_traverse(Qlist) {
    
        printf("    element %d: Val = %d, key = %d\n", ++i, Qlist->get()->val.i, Qlist->get()->key);
    }
    }
    I know I haven't explained this well at all, but if anyone can see where I need to change something or can give me advice on how to do this, I would greatly appreciate it.

    Thanks!

    P.S. The append, dl_traverse, etc. are functions from a tool my professor gave us that we need to use. If need be, I can explain more about how it works.

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,659
    It's really hard to say without seeing more of the implementation, but there does seem to be some flawed logic going on there. Post some more code.

    >>delete olddata;
    >>olddata = new Queue2;

    I know you just have that there for 'testing', but you definitely do not want to do that, since you inserted the node before that call, which renders it invalid in the process.



    ITSA
    Socket Library!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 08:17 AM
  2. Fixing my program
    By Mcwaffle in forum C Programming
    Replies: 5
    Last Post: 11-05-2008, 02:55 AM
  3. Priority Queue Help
    By cjwenigma in forum C++ Programming
    Replies: 6
    Last Post: 11-14-2007, 11:48 PM
  4. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 09:09 PM
  5. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 11:39 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21