Writing a priority queue with a max heap structure in c++ -
i writing priority queue max heap structure assignment school. can either write array or can use vector. chose vector. assignment this, user chooses options menu either wants add,print, or view elements. when user chooses add gets ask wants added, instructor, student, or ta. can enter i,i,t,t,s,s. instructor having highest priority if user chooses option print , there instructor in queue gets go first. ta having second highest priority if there ta , student in queue, ta goes first. if there is more 1 instructor queue acts normal queue. have written of it, or tried. got max heap implementation textbook since provide one. problem this, when have more 1 item in priority queue , choose print, crashes , gives me vector subscript out of range exception. been trying fix , no luck. also, when try print elements in queue or print them, needs job# name of person. can me find way implement that.
#pragma once #include <vector> struct heap { std::vector<int> m_elements; void reheapdown(int, int); void reheapup(int, int); void swap(int& a, int& b); }; #include "heap.h" void heap::reheapdown(int index, int bottom) { int maxchild, rightchild, leftchild; leftchild = index * 2 + 1; rightchild = index * 2 + 2; if (leftchild <= bottom) { if (leftchild == bottom) maxchild = leftchild; else { if (m_elements[leftchild] <= m_elements[rightchild]) maxchild = rightchild; else maxchild = leftchild; } if (m_elements[index] < m_elements[maxchild]) { swap(m_elements[index], m_elements[maxchild]); reheapdown(maxchild, bottom); } } } void heap::reheapup(int index, int bottom) { int parent; if (bottom > index) { parent = (bottom - 1) / 2; if (m_elements[parent] < m_elements[bottom]) { swap(m_elements[parent], m_elements[bottom]); reheapup(index, parent); } } } void heap::swap(int& a, int& b) { int temp; temp = a; = b; b = temp; } #include <iostream> #include "heap.h" #pragma once class pqtype { private: heap m_items; public: bool isempty() const; void enqueue(int, std::string); void dequeue(int, std::string); void printelements(); }; #include "pqtype.h" bool pqtype::isempty() const { return m_items.m_elements.empty(); } void pqtype::enqueue(int newitem, std::string lname) { if (lname == "student") { m_items.m_elements.push_back(newitem); m_items.reheapup(0, m_items.m_elements.size() - 1); } else if (lname == "ta") { m_items.m_elements.push_back(newitem); m_items.reheapup(0, m_items.m_elements.size() - 1); } else if (lname == "instructor") { m_items.m_elements.push_back(newitem); m_items.reheapup(0, m_items.m_elements.size() - 1); } } void pqtype::dequeue(int item, std::string lname) { if (isempty()) std::cout << "no jobs print\n"; else { m_items.m_elements[0] = m_items.m_elements.back(); std::cout << "now printing job#" << m_items.m_elements[item - 1] << " " << lname.c_str() << std::endl; m_items.m_elements.pop_back(); m_items.reheapdown(0, item - 1); } } void pqtype::printelements() { if (isempty()) std::cout << "no jobs print\n"; else { (int = 0; < m_items.m_elements.size(); i++) { std::cout << "job#" << m_items.m_elements[i] << std::endl; } } } #include"pqtype.h" struct person { int m_priority; std::string m_name; person() { m_priority = 0; m_name = " "; } }; int showmenu(); void addjobs(pqtype&, person&); void printjobs(pqtype&, person&); void viewjobs(pqtype&); int main() { int option; person p; pqtype pq; { option = showmenu(); switch (option) { case 1: addjobs(pq, p); break; case 2: printjobs(pq, p); break; case 3: viewjobs(pq); break; case 4: break; default: std::cout << "wrong input\n"; break; } } while (option != 4); return 0; } int showmenu() { int choice; std::cout << " 1.)add job\n"; std::cout << " 2.)print job\n"; std::cout << " 3.)view jobs\n"; std::cout << " 4.)exit\n"; std::cout << " enter choice: "; std::cin >> choice; return choice; } void addjobs(pqtype& pq, person& per) { char jobchoice; std::cout << "who job ( instructor(i or i), ta(t or t), student(s or s) :"; std::cin >> jobchoice; if (jobchoice == 's' || jobchoice == 's') { per.m_priority++; per.m_name = "student"; pq.enqueue(per.m_priority, per.m_name); } else if (jobchoice == 't' || jobchoice == 't') { per.m_priority++; per.m_name = "ta"; pq.enqueue(per.m_priority, per.m_name); } if (jobchoice == 'i' || jobchoice == 'i') { per.m_priority++; per.m_name = "instructor"; pq.enqueue(per.m_priority, per.m_name); } } void printjobs(pqtype& pq, person& p) { pq.dequeue(p.m_priority, p.m_name); } void viewjobs(pqtype& pq) { pq.printelements(); }
in original code index used inside dequeue() accessing vector doesn't seem initialised in right way. let's assume have added 2 entries list. in case value of p.m_priority inside main() 2. you're calling printjobs() first time. printjobs() calls pq.dequeue(p.m_priority, p.m_name), dequeue() gets p.m_priority parameter item. keep in mind item has value 2.
m_items.m_elements[0] = m_items.m_elements.back(); std::cout << "now printing job#" << m_items.m_elements[item - 1] << " " << lname.c_str() << std::endl; m_items.m_elements.pop_back(); you're accessing std::vector using index of item - 1. works first time, there 2 elements in list. in call, there pop_back() done on list, decreases size one. next time call printjobs(), given parameter item won't have changed, still has value 2. when access itemlist, there no longer index of 1, , subscript out of range exception thrown.
there no fixed priorities assigned 3 entry types in original version, added these (see addjobs() ).
so possible solution store person's name this:
struct person { int m_priority; std::string m_name; person() { m_priority = 0; m_name = " "; } }; struct heap { std::vector<person> m_elements; void reheapdown(int, int); void reheapup(int, int); void swap(person& a, person& b); }; void heap::reheapdown(int index, int bottom) { int maxchild, rightchild, leftchild; leftchild = index * 2 + 1; rightchild = index * 2 + 2; if (leftchild <= bottom) { if (leftchild == bottom) maxchild = leftchild; else { if (m_elements[leftchild].m_priority <= m_elements[rightchild].m_priority) maxchild = rightchild; else maxchild = leftchild; } if (m_elements[index].m_priority < m_elements[maxchild].m_priority) { swap(m_elements[index], m_elements[maxchild]); reheapdown(maxchild, bottom); } } } void heap::reheapup(int index, int bottom) { int parent; if (bottom > index) { parent = (bottom - 1) / 2; if (m_elements[parent].m_priority < m_elements[bottom].m_priority) { swap(m_elements[parent], m_elements[bottom]); reheapup(index, parent); } } } void heap::swap(person& a, person& b) { person temp; temp = a; = b; b = temp; } #include <iostream> class pqtype { private: heap m_items; public: bool isempty() const; void enqueue(person); void dequeue(); void printelements(); }; bool pqtype::isempty() const { return m_items.m_elements.empty(); } void pqtype::enqueue(person newitem) { if (!newitem.m_name.compare("student")) { m_items.m_elements.push_back(newitem); m_items.reheapup(0, m_items.m_elements.size() - 1); } else if (!newitem.m_name.compare("ta")) { m_items.m_elements.push_back(newitem); m_items.reheapup(0, m_items.m_elements.size() - 1); } else if (!newitem.m_name.compare("instructor")) { m_items.m_elements.push_back(newitem); m_items.reheapup(0, m_items.m_elements.size() - 1); } } void pqtype::dequeue() { if (isempty()) std::cout << "no jobs print\n"; else { person front = m_items.m_elements.front(); std::cout << "now printing job#" << front.m_priority << " " << front.m_name.c_str() << std::endl; m_items.m_elements.erase(m_items.m_elements.begin()); m_items.reheapdown(0, m_items.m_elements.size() - 1); } } void pqtype::printelements() { if (isempty()) std::cout << "no jobs print\n"; else { (int = 0; < m_items.m_elements.size(); i++) { std::cout << "job#" << m_items.m_elements[i].m_priority << " " << m_items.m_elements[i].m_name.c_str() << std::endl; } } } int showmenu(); void addjobs(pqtype&, person&); void printjobs(pqtype&, person&); void viewjobs(pqtype&); int showmenu() { int choice; std::cout << " 1.)add job\n"; std::cout << " 2.)print job\n"; std::cout << " 3.)view jobs\n"; std::cout << " 4.)exit\n"; std::cout << " enter choice: "; std::cin >> choice; return choice; } void addjobs(pqtype& pq, person& per) { char jobchoice; std::cout << "who job ( instructor(i or i), ta(t or t), student(s or s) :"; std::cin >> jobchoice; if (jobchoice == 's' || jobchoice == 's') { per.m_priority = 0; per.m_name = "student"; pq.enqueue(per); } else if (jobchoice == 't' || jobchoice == 't') { per.m_priority = 1; per.m_name = "ta"; pq.enqueue(per); } if (jobchoice == 'i' || jobchoice == 'i') { per.m_priority = 2; per.m_name = "instructor"; pq.enqueue(per); } } void printjobs(pqtype& pq) { pq.dequeue(); } void viewjobs(pqtype& pq) { pq.printelements(); } int main() int option; person p; pqtype pq; { option = showmenu(); switch (option) { case 1: addjobs(pq, p); break; case 2: printjobs(pq); break; case 3: viewjobs(pq); break; case 4: break; default: std::cout << "wrong input\n"; break; } } while (option != 4); return 0 } are sure methods reheapup , reheapdown meet requirements? , shouldn't there distinction between job number , priority?
Comments
Post a Comment