Hướng dẫn priority queue c++ - hàng đợi ưu tiên C++

Giới thiệu priority_queue:

Priority queue là một loại container adaptor, được thiết kế đặc biệt để phần tử ở đỉnh luôn luôn là phần tử có độ ưu tiên lớn nhất 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ì.

Khác với queue, priority_queue không có khái nhiệm front, back mà chỉ có khái nhiệm top tương tự như stack.

Hướng dẫn priority queue c++ - hàng đợi ưu tiên C++

Độ ưu tiên có thể sử dụng các phép toán trong thư viện functional hoặc lập trình viên có thể tự định nghĩa.

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).

Một số phép toán so sánh của thư viện functional:

equal_to Bằng (==)
not_equal_to Không bằng (!=)
greater Lớn hơn (>)
less Nhỏ hơn (
greater_equal Lớn hơn hoặc bằng (>=)
less_equal Nhỏ hơn hoặc bằng (

Để 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 priority_queue:

Trong C++ không có thư viện priority_queue, do đó, để sử dụng priority_queue,  ta cần khai báo thư viên queue:

#include

Khai báo với phép toán mặc định là less:

priority_queue myPriorityQueue;

Ta có thể tưởng tượng priority_queue tương tự như stack, do đó, phần tử có độ ưu tiên lớn nhất sẽ nằm về phía bên phải (Như hình ảnh ở phần giới thiệu priority_queue). Do đó, khi sử dụng phép toán less, phần tử độ ưu tiên cao nhất là phần tử có giá trị lớn nhất.

Khai báo với phép toán khác:

Ví dụ: sử dụng phép toán greater của thư viện functional

priority_queue myPriorityQueue ;

Khi sử dụng phép toán greater, phần tử độ ưu tiên cao nhất là phần tử có giá trị nhỏ nhất.

Khai báo sử dụng class so sánh tự định nghĩa:

Ta sử dụng một struct kết hợp với nạp chồng toán tử dấu ngoặc đơn như ví dụ bên dưới:

structcmp{ cmp{

booloperator()(inta,intb){returna operator() (int a,int b) {return a<b;}

};;

intmain(){ main() {

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

}

Các phương thức thành viên:

Capacity:
size() Trả về số lượng phần tử của priority_queue
empty() Trả về true(1) nếu priority_queue rỗng, ngược lại là false (0)
Element access:
top() Truy xuất phần tử ở đỉnh priority_queue (phần tử có độ ưu tiên lớn nhất)
Modifier:
push (const x) Thêm phần tử có giá trị x vào priority_queue. Kích thước priority_queue tăng thêm 1.
pop () Loại bỏ phần tử ở đỉnh priority_queue. Kích thước priority_queue giảm đi 1.

Capacity:

size()

Trả về số lượng phần tử của priority_queue.

Ví dụ: Tạo một priority_queue có 5 phần tử bất kì và in ra số lượng phần tử của priority_queue này.

1

2

3

4

5

6

7

8

9

10

11

12

#include

#include

Khai báo với phép toán mặc định là less:namespace std;

intmain() main()

priority_queue myPriorityQueue;

    priority_queuemyPriorityQueue;priority_queue<int> myPriorityQueue;

    for(inti=0;ifor(int i =0 ; i < 5; i++) {

Ta có thể tưởng tượng priority_queue tương tự như stack, do đó, phần tử có độ ưu tiên lớn nhất sẽ nằm về phía bên phải (Như hình ảnh ở phần giới thiệu priority_queue). Do đó, khi sử dụng phép toán less, phần tử độ ưu tiên cao nhất là phần tử có giá trị lớn nhất.myPriorityQueue.push(100) ; // 100 100 100 100 100

    }}

    coutcout << “The size of priority_queue is: “ << myPriorityQueue.size()<< endl;

    return0;return 0;

}

Các phương thức thành viên:

size()

priority_queuemyPriorityQueue(5);<int>myPriorityQueue(5) ;

Trả về số lượng phần tử của priority_queue

empty()

priority_queuemyPriorityQueue(5,100) <int> myPriorityQueue (5,100)

Trả về true(1) nếu priority_queue rỗng, ngược lại là false (0)

empty()

Element access:

top()

1

2

3

4

5

6

7

8

9

10

11

12

13

14

#include

#include

Khai báo với phép toán mặc định là less:namespace std;

intmain() main()

priority_queue myPriorityQueue;

    priority_queuemyPriorityQueue;priority_queue<int> myPriorityQueue ;

Ta có thể tưởng tượng priority_queue tương tự như stack, do đó, phần tử có độ ưu tiên lớn nhất sẽ nằm về phía bên phải (Như hình ảnh ở phần giới thiệu priority_queue). Do đó, khi sử dụng phép toán less, phần tử độ ưu tiên cao nhất là phần tử có giá trị lớn nhất.if( myPriorityQueue.empty()) {

        coutcout<<“priority_queue is empty! “<<endl ;

Khai báo với phép toán khác:}

Ví dụ: sử dụng phép toán greater của thư viện functionalelse {

        coutcout<<“priority_queue is not empty! “<<endl ;

Khai báo với phép toán khác:}

    return0;return 0;

}

Element access:

top()

top()

Truy xuất phần tử ở đỉnh priority_queue (phần tử có độ ưu tiên lớn nhất)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

#include

#include

Khai báo với phép toán mặc định là less:namespace std;

intmain() main()

priority_queue myPriorityQueue;

    priority_queuemyPriorityQueue;priority_queue<int> myPriorityQueue ;

Ta có thể tưởng tượng priority_queue tương tự như stack, do đó, phần tử có độ ưu tiên lớn nhất sẽ nằm về phía bên phải (Như hình ảnh ở phần giới thiệu priority_queue). Do đó, khi sử dụng phép toán less, phần tử độ ưu tiên cao nhất là phần tử có giá trị lớn nhất.// creat priority_queue

    myPriorityQueue.push(5);myPriorityQueue.push(5) ;

    myPriorityQueue.push(3);myPriorityQueue.push(3) ;

    myPriorityQueue.push(2);myPriorityQueue.push(2) ;

    myPriorityQueue.push(4);myPriorityQueue.push(4) ;

    myPriorityQueue.push(1);myPriorityQueue.push(1) ;

Khai báo với phép toán khác:// print priority_queue

Ví dụ: sử dụng phép toán greater của thư viện functionalwhile(!myPriorityQueue.empty()) {

    coutcout<<myPriorityQueue.top()<<” “  ;

    myPriorityQueue.pop();myPriorityQueue.pop() ;

Khai báo với phép toán khác:}

    return0;return 0;

}

Nhận xét: Mặc dù thứ tự ta cho vào priorty_queue là 5,3,2,4,1 không được sắp xếp, tuy nhiên, khi in ra kết quả, ta có thứ tự giảm dần 5,4,3,2,1(Độ ưu tiên là in số lớn nhất, vì độ ưu tiên mặc định là less).

Ví dụ 2: Tạo priority_queue có 5 phần tử có giá trị lần lượt là  5,3,2,4,1 với độ ưu tiên là greater. Hãy in ra các phần tử theo thứ tự độ ưu tiên cao nhất đến thấp nhất.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

#include

using namespacestd;namespace std;

intmain() main()

{

    priority_queuemyPriorityQueue;priority_queue<int,vector<int>,greater<int> > myPriorityQueue ;

    // creat priority_queue// creat priority_queue

    myPriorityQueue.push(5);myPriorityQueue.push(5) ;

    myPriorityQueue.push(3);myPriorityQueue.push(3) ;

    myPriorityQueue.push(2);myPriorityQueue.push(2) ;

    myPriorityQueue.push(4);myPriorityQueue.push(4) ;

    myPriorityQueue.push(1);myPriorityQueue.push(1) ;

    // print priority_queue// print priority_queue

   while(!myPriorityQueue.empty()){while(!myPriorityQueue.empty()) {

    coutcout<<myPriorityQueue.top()<<” “  ;

    myPriorityQueue.pop();myPriorityQueue.pop() ;

   }}

    return0;return 0;

}

Nhận xét: kết quả in ra theo thứ tự tăng dần 1,2,3,4,5 vì độ ưu tiên là greater (lớn hơn).

Ví dụ 2: Tạo priority_queue có 5 phần tử có giá trị lần lượt là  5,3,2,4,1 với độ ưu tiên được mô tả bởi phương thức so sánh :

structcmp{ cmp{

booloperator()(inta,intb){returna operator() (int a,int b) {return a<b;}

};;

Hãy in ra các phần tử theo thứ tự độ ưu tiên cao nhất đến thấp nhất.

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

#include

#include

using namespacestd;namespace std;

structcmp{ cmp{

    booloperator()(inta,intb){bool operator() (int a,int b) {

        returnareturn a<b;

    }}

};;

intmain() main()

{

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

    // creat priority_queue// creat priority_queue

    myPriorityQueue.push(5);myPriorityQueue.push(5) ;

    myPriorityQueue.push(3);myPriorityQueue.push(3) ;

    myPriorityQueue.push(2);myPriorityQueue.push(2) ;

    myPriorityQueue.push(4);myPriorityQueue.push(4) ;

    myPriorityQueue.push(1);myPriorityQueue.push(1) ;

    // print priority_queue// print priority_queue

   while(!myPriorityQueue.empty()){while(!myPriorityQueue.empty()) {

    coutcout<<myPriorityQueue.top()<<” “  ;

    myPriorityQueue.pop();myPriorityQueue.pop() ;

   }}

    return0;return 0;

}

Modifier:

Nhận xét: kết quả in ra theo thứ tự tăng dần 1,2,3,4,5 vì độ ưu tiên là greater (lớn hơn).

Ví dụ 2: Tạo priority_queue có 5 phần tử có giá trị lần lượt là  5,3,2,4,1 với độ ưu tiên được mô tả bởi phương thức so sánh :

};

Hãy in ra các phần tử theo thứ tự độ ưu tiên cao nhất đến thấp nhất.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

#include

#include

using namespacestd;namespace std;

intmain() main()

{

    priority_queuemyPriorityQueue;priority_queue<int> myPriorityQueue;

    // creat priority_queueint n;  // size of queue

    coutcout<<“Size: “ ;

    cin>>n;cin>>n ;

    // print priority_queue// create queue

    inttempNumber  ;int tempNumber  ;

    for(inti=0;ifor(int i = 0 ; i<n; i++) {

        cin>>tempNumber;cin>>tempNumber ;

        myPriorityQueue.push(tempNumber);myPriorityQueue.push(tempNumber) ;

    }}

   while(!myPriorityQueue.empty()){

    for(inti=0;ifor(int i = 0 ; i<n; i++) {

        tempNumber=myPriorityQueue.top();tempNumber = myPriorityQueue.top() ;

        myPriorityQueue.pop();myPriorityQueue.pop();

        coutcout<<tempNumber<<” “ ;

    }}

    return0;return 0;

}

   }

Nhận xét: kết quả in ra theo thứ tự tăng dần 1,2,3,4,5 vì độ ưu tiên là greater (lớn hơn).

Ví dụ 2: Tạo priority_queue có 5 phần tử có giá trị lần lượt là  5,3,2,4,1 với độ ưu tiên được mô tả bởi phương thức so sánh :

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

#include

#include

using namespacestd;namespace std;

intmain() main()

{

    priority_queuemyPriorityQueue;priority_queue<int> myPriorityQueue;

    // creat priority_queueint n; // size of priority_queue

    coutcout<<“Size: “ ;

    cin>>n;cin>>n ;

    // print priority_queue// create priority_queue

    inttempNumber  ;int tempNumber  ;

    for(inti=0;ifor(int i = 0 ; i<n; i++) {

        cin>>tempNumber;cin>>tempNumber ;

        myPriorityQueue.push(tempNumber);myPriorityQueue.push(tempNumber ) ;

    }}

   while(!myPriorityQueue.empty()){// delete element

   }for(int i = 0 ; i<n/2; i++) {

        myPriorityQueue.pop();myPriorityQueue.pop() ;

    }}

    // print priority_queue// print priority_queue

   while(!myPriorityQueue.empty()){n = myPriorityQueue.size() ; // after using pop(), the size of priority_queue < n

    for(inti=0;ifor(int i = 0 ; i<n; i++) {

        tempNumber=myPriorityQueue.top();tempNumber = myPriorityQueue.top() ;

        myPriorityQueue.pop();myPriorityQueue.pop();

        coutcout<<tempNumber<<” “ ;

    }}

    return0;return 0;

}