Priority queue (hàng đợi ưu tiên) trong C++

Priority queue là một loại container adaptor, được thiết kế đặc biệt để phần tử ở đầu luôn luôn lớn nhất (theo một quy ước về độ ưu tiên nào đó) so với các phần tử khác.

Nó giống như một heap, mà ở đây là heap max, tức là phần tử có độ ưu tiên lớn nhất có thể được lấy ra và các phần tử khác được chèn vào bất kì.

Phép toán so sánh mặc định khi sử dụng priority queue là phép toán less (Xem thêm ở thư viện functional)

Để sử dụng priority queue một cách hiệu quả, các bạn nên học cách viết hàm so sánh để sử dụng cho linh hoạt cho từng bài toán.

Khai báo: #include <queue>

/*Dạng 1 (sử dụng phép toán mặc định là less)*/ 
priority_queue <int> pq;

/* Dạng 2 (sử dụng phép toán khác) */
priority_queue <int,vector<int>,greater<int> > q; //phép toán greater

Phép toán khác cũng có thể do người dùng tự định nghĩa. Ví dụ:

Cách khai báo ở dạng 1 tương đương với:

/* Dạng sử dụng class so sánh tự định nghĩa */ struct cmp{

bool operator() (int a,int b) {return a<b;}

};

main() {

…

priority_queue <int,vector<int>,cmp > q;

}

Các hàm thành viên:

  • size : trả về kích thước hiện tại của priority queue. ĐPT O(1)
  • empty : true nếu priority queue rỗng, và ngược lại. ĐPT O(1).
  • push : đẩy vào priority queue. ĐPT O(logN).
  • pop: loại bỏ phần tử ở đỉnh priority queue. ĐPT O(logN).
  • top : trả về phần tử ở đỉnh priority queue. ĐPT O(1).

Chương trình demo:

#include <iostream>
 
#include <queue>
 
#include <vector>
 
using namespace std;
 
main() {
 
    priority_queue <int> p;	// p={}
 
    p.push(1);	// p={1}
 
    p.push(5);	// p={1,5}
 
    cout << p.top() << endl; // In ra 5
 
    p.pop();	// p={1}
 
    cout << p.top() << endl; // In ra 1
 
    p.push(9);	// p={1,9}
 
    cout << p.top() << endl; // In ra 9
 
    system("pause");
 
}

Chương trình Demo 2:

#include <iostream>
 
#include <queue>
 
#include <vector>
 
using namespace std;
 
main() {
    priority_queue < int , vector <int> , greater <int> > p;	// p={}
    p.push(1);     //p={1}
    p.push(5);     //p={1,5}
    cout << p.top() << endl;    //In ra 1
    p.pop();       //p={5}
    cout << p.top() << endl;     //In ra 5
    p.push(9);    //p={5,9}
    cout << p.top() << endl; // In ra 5
    system("pause");
}

Chương trình Demo 3:

#include <iostream>
 
#include <queue>
 
#include <vector>
 
using namespace std;
 
struct cmp{
    bool operator() (int a,int b) {return a<b;}
};
 
main() {
    priority_queue < int , vector <int> , cmp > p;	// p={}
    p.push(1);    //p={1}
    p.push(5);    //p={1,5}
    cout << p.top() << endl;     //In ra 1
    p.pop();    //p={5}
    cout << p.top() << endl;     //In ra 5
    p.push(9);    //p={5,9}
    cout << p.top() << endl; // In ra 5
system("pause");
}
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*