寻找队列中的最大值或最小值，出队。
优先队列的底层实现：堆；（对于堆的底层实现，面试时经常会出）。
C++中的优先队列容器：priority_queue
1. 默认从大到小排列：（最大堆）
#include #include #include using namespace std;int main() { srand(time(NULL)); //产生随机数 priority_queue pq; for (int i = 0; i < 10;i++) { int num = rand() % 100; pq.push(num); cout << "insert" << num << "in priority queue." << endl; } while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } return 0;}
2. 小顶堆
#include #include #include using namespace std;int main() { srand(time(NULL)); //产生随机数 priority_queue
, greater
> pq2; //最小堆，传入为int型，底层数据结构实现一般为vector，比较函数greater for (int i = 0; i < 10;i++) { int num = rand() % 100; pq2.push(num); cout << "insert" << num << "in priority queue." << endl; } while (!pq2.empty()) { cout << pq2.top() << " "; pq2.pop(); } return 0;}
3. 自定义比较函数：
#include #include #include using namespace std; struct myCmp{ bool operator()(int a, int b){ return a % 10 < b % 10; //比较个位数，个位数越大越靠前 }};int main() { srand(time(NULL)); //产生随机数 priority_queue pq; for (int i = 0; i < 10;i++) { int num = rand() % 100; pq.push(num); cout << "insert" << num << "in priority queue." << endl; } while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } cout << endl << endl; priority_queue
> pq2; //底层是最小堆 for (int i = 0; i < 10;i++) { int num = rand() % 100; pq2.push(num); cout << "insert" << num << "in priority queue." << endl; } while (!pq2.empty()) { cout << pq2.top() << " "; pq2.pop(); } //使用自定义Comparator的priority queue priority_queue
