|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include <iostream> #include <vector> #include <algorithm> // A class to represent a priority queue class PriorityQueue { private: std::vector<int> data; // Helper function to heapify the tree void heapify_up(int index) { if (index == 0) return; // Base case: root node int parent = (index - 1) / 2; if (data[index] > data[parent]) { std::swap(data[index], data[parent]); heapify_up(parent); } } void heapify_down(int index) { int leftChild = 2 * index + 1; int rightChild = 2 * index + 2; int largest = index; if (leftChild < data.size() && data[leftChild] > data[largest]) { largest = leftChild; } if (rightChild < data.size() && data[rightChild] > data[largest]) { largest = rightChild; } if (largest != index) { std::swap(data[index], data[largest]); heapify_down(largest); } } public: // Insert a new element into the priority queue void push(int value) { data.push_back(value); heapify_up(data.size() - 1); } // Remove and return the highest priority element int pop() { if (data.empty()) { throw std::out_of_range("Priority Queue is empty"); } int root = data.front(); data[0] = data.back(); data.pop_back(); heapify_down(0); return root; } // Return the highest priority element without removing it int top() const { if (data.empty()) { throw std::out_of_range("Priority Queue is empty"); } return data.front(); } // Check if the priority queue is empty bool empty() const { return data.empty(); } }; int main() { PriorityQueue pq; // Inserting elements into the priority queue pq.push(5); pq.push(15); pq.push(10); pq.push(30); pq.push(20); std::cout << "Top element: " << pq.top() << std::endl; // Removing elements from the priority queue std::cout << "Popped element: " << pq.pop() << std::endl; std::cout << "Popped element: " << pq.pop() << std::endl; std::cout << "Top element after popping: " << pq.top() << std::endl; return 0; } |
Explanation
- Priority Queue Class:
- The
PriorityQueueclass uses a vector (std::vector<int> data) to store the elements. It maintains a max-heap, where the highest priority element is always at the root (index 0). - heapify_up: This method ensures the heap property is maintained after inserting a new element by comparing the newly added element with its parent and swapping if necessary.
- heapify_down: This method is used to maintain the heap property after removing the root element by comparing the new root with its children and swapping if necessary.
- The
- Push Operation:
- The
push(int value)method inserts a new element into the priority queue. It adds the element at the end of the vector and then callsheapify_upto maintain the heap property.
- The
- Pop Operation:
- The
pop()method removes and returns the highest priority element (the root). It replaces the root with the last element and then callsheapify_downto maintain the heap property.
- The
- Top Operation:
- The
top()method returns the highest priority element without removing it.
- The
- Empty Operation:
- The
empty()method checks if the priority queue is empty.
- The