Noob question to hlep getting started with priority queue

This is a discussion on Noob question to hlep getting started with priority queue within the C++ Programming forums, part of the General Programming Boards category; You really need to decide on one way to do it. It's a choice between map and vector and either ...

  1. #31
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,525
    You really need to decide on one way to do it. It's a choice between map and vector and either will work.

    So putting my pairs into the vector would "build the heap"
    or do I need to store the mapping elements into the vector and then "build a heap".
    If the priority is the key, a map would work by itself, because it would order the strings internally by their priority.

    A sub question, is can I take my struct as white flags demonstrated, make a vector from within my priority queue class and then transmit the information/updates... or am I waaaaaaaaayyyyy offfffff?
    If you decided to use a vector in the priority queue class, you would have to make an algorithm to build a heap. That means reordering the elements in the array such that they conform to the heap property: i.e., heap sort.
    Last edited by whiteflags; 09-20-2013 at 08:33 PM.

  2. #32
    Registered User
    Join Date
    Sep 2012
    Posts
    86
    Well mapping sounds much easier and efficient, and I can do all needed operations such as update, remove, etc?

    The way you're talking, you make it seem like I'm making the assignment way too difficult.
    Last edited by carpeltunnel; 09-20-2013 at 09:05 PM.

  3. #33
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,525
    Yes, the map class is well documented and it does all of those things.

  4. #34
    Registered User
    Join Date
    Sep 2012
    Posts
    86
    Quote Originally Posted by whiteflags View Post
    Yes, the map class is well documented and it does all of those things.
    I guess my main problem is making the association between the mapping and the requirement for an array based heap.

  5. #35
    Registered User
    Join Date
    Sep 2012
    Posts
    86
    OK, I'm going to bite the bullet and post my code. I would like to preface to say the original deadline is passed so I tried to put a lot of related material in before turning in (I know bad, but I needed something), next deadline is tomorrow I haven't procrastinated I've just struggled with this tremendously.

    If someone can tell me what's excess, or what flow I need, anything, I just need to figure this out and make it click.

    Code:
    #include <string>
    #include <queue>
    #include <iostream>
    #include <fstream>
    #include <conio.h>
    #include <queue>
    #include <map>
    using namespace std;
    struct queue_element {
     string data;
     float priority;
     //friend istream& operator >> (istream& comm, queue_element& elem);
      
    };
     /*istream& operator >> (istream& instr, queue_element& elem) {    
      queue_element result;    
      if (comm >> result.data >> result.priority) {        
       elem = result;    
      }    
      return comm;
    }*/
    int main(int argc,const char *argv[])
    {    
     priority_queue map<string, float> pq;
     
     int i = 0;
     if (argc < 3)    
     {        
      std::cerr << "Usage: myprog inputfile outputfile\n";        
      return 1;    
     }  
     
     
     ifstream inFile(argv[1]); 
     ofstream outFile(argv[2]); 
     char command;
     string line;
     int counter;
     while(getline(inFile, line)){
      stringstream buffer(line);
      buffer >> command;
      queue_element elem;
      while (buffer >> elem){
      }
     }
     while (command != /0)
     {
      switch(command)
      {
      case B:
       //.build_heap;
       break;
      case A:
       //insert function for new objects
       break;
      case U:
       //update objects and order in heap
       break;
      case R:
       //remove best object
       break;
      case D:
       //dump heap (print contents in order)
       break;
      case P:
       for ( i = 1; i+=)
       {
       x = pq.find[i];
       if (x != pq.end()) //found key
        cout << p->first << p-> second << endl; 
       else
        cout << "Item not found" << endl;
       break;
      }
     }
     
     return 0;
    }
    Code:
    #ifndef PRIORITY_QUEUE_H
    #define PRIORITY_QUEUE_H
    #include <string>
    #include <iostream>
    #include <map>
    #include <vector>
    #include <iterator>
    using namespace std;
    class priority_queue 
    {
      
    public:
      priority_queue(int); //constructor
      ~priority_queue();    //destructor
      void build_heap(struct, map); //take objects and put into min-heap
      void extract_max();    //remove the string of "best object" and delete from heap array
      
      void heapsort()
      void insert(vector);
      
      bool leaf(size i) const;
      void setheapsize (int);
      void setpair (struct);
      
      size parent_index(size i) const; //do I even need these?
      size big_child_index(size i) const;
     
    private:
     struct queue_element;
     map<string, float> pq;
     
     
    };
    #endif
    Code:
    #include <assert.h>    // Provides assert function
    #include <iomanip>   // Provides setw
    #include <iostream>  // Provides cin, cout
    #include "PriorityQueue.h"
    using namespace std;
    
    //constructor
    PriorityQueue::PriorityQueue(map)
    {
     
    }
    void heapify(map)
    {
        int left=(2*priority);
        int right=(2*priority)+1;
        int large;
        if((left<=hs)&&(a[left]>a[num]))
        {
            large=left;
        }
        else
        {
            large=priority;
        }
        if((right<=hs)&&(a[right]>a[large]))
        {
            large=right;
        }
        if(num!=large)
        {
            swap(a[num],a[large]);
            heapify(large);
        }
    }
    void PriorityQueue::build_heap()
    {
        for(int i=n/2;i>0;i--)
        {
            heapify(i);
        }
    }
    void PriorityQueue::heapsort()
    {
        build_heap();
        hs=n;
        for(int i=hs;i>1;i--)
        {
            swap(a[1],a[i]);
            hs--;
            heapify(1);
        }
    }
    void PriorityQueue::insert(const Item& entry, int priority)
    {
        if(pair==0)
        {
            heap[pair].data= entry;
            heap[pair].priority= priority;
            pair++;
        }
        else
        {
            heap[pair].data= entry;
            heap[pair].priority= priority;
            i= pair;
            pair++;
            while(parent_priority(i)<priority)
            {
                swap_with_parent(i);
                i=parent_index(i);
            }
        }
    }
    PriorityQueue::Item PriorityQueue::extract_max( )
    {
        assert(pair>0);
        if(pair==1)
        {
           max = heapelem[1];
        heapelem[1] = heapelem[size];
        size = size -1;
        MAX-HEAPIFY (heapelem, 1)
        return max;
        }
    }
    bool PriorityQueue::leaf(size i) const
    {    
        if(((2*i)+1)>pair)
            return 1;
        else 
            return 0;
    }
    size PriorityQueue::parent_index(size i) const
    {
        return (i-1)/2;
    }
    size PriorityQueue::big_child_index(size i) const
    {
        assert(!leaf(i));
        if((2*i)+2<pair)
        {
            if(heap[(2*i)+1].priority>heap[(2*i)+2].priority)
            {
                return (2*i)+1;
            }
            else
            {
                return (2*i)+2;
            }
        }
        else
        {
            return(2*i)+1;
        }
    }

  6. #36
    Registered User
    Join Date
    Sep 2012
    Posts
    86
    I guess a big help would be what do I need to do in main, and what do I need to do in my class.

  7. #37
    Registered User
    Join Date
    Sep 2012
    Posts
    86
    Code:
    #include <string>
    #include <sstream>
    #include <iostream>
    #include <fstream>
    using namespace std;
    struct queue_element {
     string data;
     float priority;
     friend ostream& operator << (ostream& outstr, const queue_element& elem);
     friend istream& operator >> (istream& instr, queue_element& elem);
      
    };
     ostream& operator << (ostream& outstr, const queue_element& elem) {    
      outstr << "priority: " << elem.priority << ", " << "data: " << elem.data << '\n';    
      return outstr;
     }
     istream& operator >> (istream& instr, queue_element& elem) {    
      queue_element result;    
      if (instr >> result.data >> result.priority) {        
       elem = result;    
      }    
      return instr;
    }
    int main(int argc,const char *argv[])
    {   
     
     ifstream inFile(argv[1]); 
     ofstream outFile(argv[2]); 
     char command;
     string line;
     while(getline(inFile, line)){
      stringstream buffer(line);
      buffer >> command;
      outFile << "command is " << command << endl;
      queue_element elem;
      while (buffer >> elem){
      outFile << '\t' << elem << '\n';
      }
     }
    I am trying to get what white flags showed to output to my file at least, but the file updates but it still blank.

    What am I do doing wrong as far as output?

  8. #38
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,968
    How exactly does it not work? How would you debug it?

    By the way, I suggest that you use a consistent number of spaces (or a single tab) for the indent level. If you choose to use spaces, I strongly recommend more than one space (4 is my default).
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #39
    Registered User
    Join Date
    Sep 2012
    Posts
    86
    but the file updates but it still blank
    Is the issue with the output file, I've looked at some of my past code that works correctly and I don't see what is wrong unless I need to index through the elements but I didn't see anything needed of that sort in the example I was provided by white flags.

    By the way, I suggest that you use a consistent number of spaces (or a single tab) for the indent level. If you choose to use spaces, I strongly recommend more than one space (4 is my default).
    Ok, I will definitely work on that, just have been too focused on look and consistency with how far behind I am ATM.

  10. #40
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,525
    Is the issue with the output file, I've looked at some of my past code that works correctly and I don't see what is wrong unless I need to index through the elements but I didn't see anything needed of that sort in the example I was provided by white flags.
    I think you aren't successfully opening the input file. That is one way an empty file is produced. My code differed from your code since I checked if the file was open before trying to read it.

    When I tested your code, it worked for me.

    The command that executes the program might look something like this:
    Code:
    C:\Users\Josh2\Documents\test\bin\Debug>test.exe ../../in.txt ../../out.txt
    
    C:\Users\Josh2\Documents\test\bin\Debug>cd ../../
    
    C:\Users\Josh2\Documents\test>dir
     Volume in drive C has no label.
     Volume Serial Number is 4839-05AF
    
     Directory of C:\Users\Josh2\Documents\test
    
    09/21/2013  03:36 PM    <DIR>          .
    09/21/2013  03:36 PM    <DIR>          ..
    09/21/2013  03:33 PM    <DIR>          bin
    09/21/2013  03:36 PM           231,796 gmon.out
    09/21/2013  03:36 PM                49 in.txt
    09/21/2013  03:33 PM             1,053 main.cpp
    09/21/2013  03:33 PM    <DIR>          obj
    09/21/2013  03:43 PM               260 out.txt
    09/21/2013  03:31 PM               723 test.cbp
                   5 File(s)        233,881 bytes
                   4 Dir(s)  678,640,443,392 bytes free
    Using relative pathing -- passing in just a name -- can be tricky. In the example, test.exe is in the Debug directory and I had to navigate back to where the in.txt file was, in the test folder. Then I changed directories to show you where the files ended up. You will have to do something similar on your machine, most likely. The prompt in a command window is actually the current working directory in windows -- other systems use ./ to refer to it.

    Also, it can be important to check your files to see if they're open, like I did in the earlier post. Printing a message when it doesn't work can actually inform you what is going on.

Page 3 of 3 FirstFirst 123
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Priority queue STL
    By dpp in forum C++ Programming
    Replies: 2
    Last Post: 01-08-2009, 01:21 AM
  2. Priority queue
    By cjwenigma in forum C++ Programming
    Replies: 6
    Last Post: 12-03-2007, 12:30 AM
  3. Priority Queue Help
    By cjwenigma in forum C++ Programming
    Replies: 6
    Last Post: 11-14-2007, 11:48 PM
  4. Priority Queue Question
    By ac251404 in forum C++ Programming
    Replies: 26
    Last Post: 08-16-2006, 11:51 AM
  5. Priority Queue
    By evotron in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 12:46 PM

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