1 #include<cstddef> //std::size_t 2 #include<algorithm> //std::swap 3 #include<vector> 4  5 template<typename T> class PriorityQueue { 6 public: 7     PriorityQueue(){} 8  9     bool empty() {10         return data.empty();11     }12 13     size_t size() {14         return data.size();15     }16 17     T& top() {18         return data.front();19     }20 21     void push(const T& val) {22         data.push_back(val);23         push_heap();24     }25 26     void pop() {27         if (data.empty())28             return;29 30         pop_heap();31         data.pop_back();32     }33 34 private:35     void push_heap() {36         int i = data.size() - 1;37         T temp = data[i];38 39         for (; i > 0 && temp > data[i / 2]; i /= 2) {40             data[i] = data[i / 2];41         }42 43         data[i] = temp;44     }45 46     void pop_heap() {47         std::swap(data[0], data[data.size() - 1]);48         int heap_end = data.size() - 2;49 50         percolatedown(0, heap_end);51     }52 53     void percolatedown(int i, int heap_end) {54         T temp = data[i];55 56         for (int child = 2 * i + 1; child <= heap_end; child = 2 * child + 1) {57             if (child < heap_end && data[child] < data[child + 1])58                 ++child;59 60             if (temp < data[child]) {61                 data[i] = data[child];62                 i = child;63             } else {64                 break;65             }66         }67 68         data[i] = temp;69     }70 71     std::vector<T> data;72 };