Thread: Priority Queue

  1. #1
    Registered User
    Join Date
    Mar 2004

    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.

    class PQueue2 {
    friend class dList<Queue2>;
            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 *);
            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
        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
                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.


    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
    Waterloo, Texas
    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.
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
        return std::pow
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;

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, 03:55 AM
  3. Priority Queue Help
    By cjwenigma in forum C++ Programming
    Replies: 6
    Last Post: 11-15-2007, 12:48 AM
  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