fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <cassert>
  4. using namespace std;
  5.  
  6. // Define pqEntry class
  7. template <class Item>
  8. class pqEntry {
  9. public:
  10.     pqEntry(int p = 0, Item data = Item()) { priority = p; this->data = data; }
  11.     friend bool operator <= (const pqEntry<Item>& a, const pqEntry<Item>& b) { return a.priority <= b.priority; }
  12.     friend bool operator < (const pqEntry<Item>& a, const pqEntry<Item>& b) { return a.priority < b.priority; }
  13.     friend bool operator > (const pqEntry<Item>& a, const pqEntry<Item>& b) { return a.priority > b.priority; }
  14.     friend bool operator >= (const pqEntry<Item>& a, const pqEntry<Item>& b) { return a.priority >= b.priority; }
  15.     Item getData() const { return data; }
  16.     int getPriority() const { return priority; }
  17.  
  18. private:
  19.     Item data;
  20.     int priority;
  21. };
  22.  
  23. // Define Heap class
  24. template <class Item>
  25. class Heap {
  26. public:
  27.     typedef Item value_type;
  28.     typedef size_t size_type;
  29.     static const size_type CAPACITY = 100;
  30.  
  31.     Heap() { used = 0; }
  32.  
  33.     void insert(const Item& entry);
  34.     void remove();
  35.     Item top() const;
  36.     bool empty() const { return used == 0; }
  37.  
  38. private:
  39.     Item data[CAPACITY];
  40.     size_type used;
  41.  
  42.     void reheap_down(size_type i);
  43.     void reheap_up(size_type i);
  44. };
  45.  
  46. // Implement Heap methods
  47. template<class Item>
  48. void Heap<Item>::insert(const Item& entry) {
  49.     assert(used < CAPACITY);
  50.     data[used] = entry;
  51.     used++;
  52.     reheap_up(used - 1);
  53. }
  54.  
  55. template<class Item>
  56. void Heap<Item>::remove() {
  57.     assert(!empty());
  58.     data[0] = data[used - 1];
  59.     used--;
  60.     reheap_down(0);
  61. }
  62.  
  63. template<class Item>
  64. Item Heap<Item>::top() const {
  65.     assert(!empty());
  66.     return data[0];
  67. }
  68.  
  69. template<class Item>
  70. void Heap<Item>::reheap_down(size_type i) {
  71.     Item temp;
  72.     if ((data[2 * i + 1] > data[2 * i + 2] && data[2 * i + 1] > data[i]) && (2 * i + 1 < used)) {
  73.         temp = data[2 * i + 1];
  74.         data[2 * i + 1] = data[i];
  75.         data[i] = temp;
  76.         reheap_down(2 * i + 1);
  77.     } else if ((data[2 * i + 1] <= data[2 * i + 2] && data[2 * i + 2] > data[i]) && (2 * i + 2 < used)) {
  78.         temp = data[2 * i + 2];
  79.         data[2 * i + 2] = data[i];
  80.         data[i] = temp;
  81.         reheap_down(2 * i + 2);
  82.     }
  83. }
  84.  
  85. template<class Item>
  86. void Heap<Item>::reheap_up(size_type i) {
  87.     Item temp;
  88.     if (i != 0 && (data[(i - 1) / 2] < data[i])) {
  89.         temp = data[i];
  90.         data[i] = data[(i - 1) / 2];
  91.         data[(i - 1) / 2] = temp;
  92.         reheap_up((i - 1) / 2);
  93.     }
  94. }
  95.  
  96. // Define PQueue class
  97. template <class Item>
  98. class PQueue {
  99. public:
  100.     void pop();
  101.     void push(const pqEntry<Item>& entry);
  102.     Item front();
  103.     bool empty();
  104.     size_t size();
  105.  
  106. private:
  107.     Heap<pqEntry<Item>> storage;
  108. };
  109.  
  110. // Implement PQueue methods
  111. template <class Item>
  112. void PQueue<Item>::pop() {
  113.     storage.remove();
  114. }
  115.  
  116. template <class Item>
  117. void PQueue<Item>::push(const pqEntry<Item>& entry) {
  118.     storage.insert(entry);
  119. }
  120.  
  121. template <class Item>
  122. Item PQueue<Item>::front() {
  123.     return storage.top().getData();
  124. }
  125.  
  126. template <class Item>
  127. bool PQueue<Item>::empty() {
  128.     return storage.empty();
  129. }
  130.  
  131. template <class Item>
  132. size_t PQueue<Item>::size() {
  133.     return storage.size();
  134. }
  135.  
  136. // Main program
  137. int main() {
  138.     PQueue<string> pq;
  139.  
  140.     // Push tasks with priorities into the priority queue
  141.     pq.push(pqEntry<string>(7, "Take out trash"));
  142.     pq.push(pqEntry<string>(9, "Do HW"));
  143.     pq.push(pqEntry<string>(10, "Get groceries"));
  144.     pq.push(pqEntry<string>(8, "Make dinner"));
  145.     pq.push(pqEntry<string>(4, "Watch TV"));
  146.  
  147.     // Display the tasks in priority order
  148.     cout << "Priority Queue (tasks with highest priority first):" << endl;
  149.  
  150.     while (!pq.empty()) {
  151.         cout << pq.front() << endl;
  152.         pq.pop();
  153.     }
  154.  
  155.     return 0;
  156. }
  157.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
45
stdout
copy 
Priority Queue (tasks with highest priority first):
Get groceries
Do HW
Make dinner
Take out trash
Watch TV
https://ideone.com/2qhcdy
language:
C++14 (gcc 8.3)
created:
17 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!