CÁCH Sử DỤNG HÀNG đợi ưu TIÊN (PRIORITY QUEUE ... - 123doc

CÁCH SỬ DỤNG HÀNG ĐỢI ƯU TIÊN PRIORITY QUEUETRONG THƯ VIỆN STL CỦA C++ Chuyên đề trình bày cách khai thác hàng đợi ưu tiên priority queue trong thư viện STL của C++ và áp dụng vào một số

CÁCH SỬ DỤNG HÀNG ĐỢI ƯU TIÊN (PRIORITY QUEUE)

TRONG THƯ VIỆN STL CỦA C++

Chuyên đề trình bày cách khai thác hàng đợi ưu tiên (priority queue) trong thư viện STL của C++ và áp dụng vào một số bài toán Tôi viết chuyên đề này nhằm mục đích

là tài liệu tham khảo cho một số trường đang trong giai đoạn chuyển dạy ngôn ngữ lập trình Free Pascal sang ngôn ngữ C++.

1 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ì.

Độ ưu tiên có thể sử dụng các phép toán trong thư viện functional hoặc 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.

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

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ả, tùy vào từng bài toán ta viết hàm so sánh để

sử dụng cho linh hoạt.

2 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 <queue>

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

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.

2.2 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 <int,vector<int>,greater<int>> 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.

2.3 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: 1

2

3

4

5

6

7

struct cmp{

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

};

int main() {

…

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

}

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

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

(phần tử có độ ưu tiên lớn nhất)

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

#include <iostream>

#include <queue>

using namespace std;

5

6

7

8

9

10

11

12

int main()

{

priority_queue<int> myPriorityQueue;

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

myPriorityQueue.push(100) ; // 100 100 100 100 100

}

cout << "The size of priority_queue is: " << myPriorityQueue.size()<< endl;

return 0;

}

Lưu ý:

Tương tự như stack, queue, ta không thể khai báo:

1 priority_queue<int>myPriorityQueue(5) ;

để khai báo 5 phần tử rỗng tương tự như vector hay list vì priority_queue không cho phép ta khai báo phần tử rỗng.

Tương tự, ta không thể khai báo:

1 priority_queue <int> myPriorityQueue (5,100)

để khai báo 5 phần tử của priority_queue có giá trị 100.

empty()

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

Ví dụ: Kiểm tra priority_queue có rỗng không và in ra thông báo tương ứng.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

#include <iostream>

#include <queue>

using namespace std;

int main()

{

priority_queue<int> myPriorityQueue ;

if( myPriorityQueue.empty()) {

cout<<"priority_queue is empty! "<<endl ;

}

else {

cout<<"priority_queue is not empty! "<<endl ;

}

return 0;

}

top()

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

Ví dụ 1: 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 mặc

đị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

#include <iostream>

#include <queue>

using namespace std;

int main()

{

priority_queue<int> myPriorityQueue ;

// creat priority_queue

myPriorityQueue.push(5) ;

10

11

12

13

14

15

16

17

18

19

myPriorityQueue.push(3) ;

myPriorityQueue.push(2) ;

myPriorityQueue.push(4) ;

myPriorityQueue.push(1) ;

// print priority_queue

while(!myPriorityQueue.empty()) {

cout<<myPriorityQueue.top()<<" " ;

myPriorityQueue.pop() ;

}

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 <queue>

using namespace std;

int main()

{

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

// creat priority_queue

myPriorityQueue.push(5) ;

myPriorityQueue.push(3) ;

myPriorityQueue.push(2) ;

myPriorityQueue.push(4) ;

myPriorityQueue.push(1) ;

// print priority_queue

while(!myPriorityQueue.empty()) {

cout<<myPriorityQueue.top()<<" " ;

myPriorityQueue.pop() ;

}

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

struct cmp{

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

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 <iostream>

#include <queue>

using namespace std;

struct cmp{

bool operator() (int a,int b) {

return a<b;

}

};

int main()

{

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

// creat priority_queue

myPriorityQueue.push(5) ;

myPriorityQueue.push(3) ;

myPriorityQueue.push(2) ;

myPriorityQueue.push(4) ;

myPriorityQueue.push(1) ;

// print priority_queue

while(!myPriorityQueue.empty()) {

cout<<myPriorityQueue.top()<<" " ;

myPriorityQueue.pop() ;

}

return 0;

}

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.

Ví dụ:

Viết chương trình cho người dùng nhập vào kích thước priorty_queue và nhập vào giá trị các phần tử In các phần tử trong priority_queue.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

#include <iostream>

#include <queue>

using namespace std;

int main()

{

priority_queue<int> myPriorityQueue;

int n; // size of queue

cout<<"Size: " ;

cin>>n ;

// create queue

int tempNumber ;

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

cin>>tempNumber ;

myPriorityQueue.push(tempNumber) ;

}

// print queue

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

tempNumber = myPriorityQueue.top() ;

myPriorityQueue.pop();

cout<<tempNumber<<" " ;

}

return 0;

}

pop ()

Loại bỏ phần tử ở đình priority_queue (phần tử cuối cùng được thêm vào priority_queue) Kích thước priority_queue giảm đi 1.

Ví dụ: Viết chương trình cho người dùng nhập vào kích thước priority_queue và nhập vào

giá trị các phần tử Sau đó, loại bỏ đi một nửa các phần tử ở đỉnh priority_queue

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 <iostream>

#include <queue>

using namespace std;

int main()

{

priority_queue<int> myPriorityQueue;

int n; // size of priority_queue

cout<<"Size: " ;

cin>>n ;

// create priority_queue

int tempNumber ;

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

cin>>tempNumber ;

myPriorityQueue.push(tempNumber ) ;

}

// delete element

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

myPriorityQueue.pop() ;

}

// print priority_queue

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

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

tempNumber = myPriorityQueue.top() ;

myPriorityQueue.pop();

cout<<tempNumber<<" " ;

}

return 0;

}

4 Một số dạng bài tập có sử dụng priority_queue

Bài1 Dijkstra - Tìm đường đi ngắn nhất trên đồ thị

Mục đích: Từ một đỉnh S, ta muốn biết độ dài đường đi ngắn nhất từ S đến tất cả các đỉnh

còn lại (trong đồ thị có hướng hoặc vô hướng).

Độ phức tạp : O (n log n).

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

#include <stdio.h>

#include <vector>

#include <queue>

using namespace std;

const int oo = 1000111000;

typedef pair<int, int> ii;

vector <ii> a[2309];

int n, m;

int d[2309];

void dijkstra(){

priority_queue <ii, vector<ii>, greater<ii>> pq;

int i, u, v, du, uv;

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

for (i=1; i<=n; i++) d[i] = oo;

d[1] = 0;

pq.push(ii(0, 1));

while (pq.size()){

u=pq.top().second;

du=pq.top().first;

pq.pop();

if (du!=d[u]) continue;

for (i=0; v=a[u][i].second; i++)

{

uv=a[u][i].first;

if (d[v]>du+uv) {

d[v]=du+uv;

pq.push(ii(d[v], v));

}

}

}

}

main(){

int p, q, i, m, w;

scanf("%d%d", &n, &m);

while (m ){

scanf("%d%d%d", &p, &q, &w);

a[p].push_back(ii(w, q));

a[q].push_back(ii(w, p));

}

for (i=1; i<=n; i++) a[i].push_back(ii(0,0));

dijkstra();

for (i=1; i<=n; i++) printf("d( 1 -> %d ) = %d\n", i, d[i]);

}

5 5

1 2 10

1 3 10

2 4 20

3 4 25

1 4 33

d( 1->1 ) = 0 d( 1->2 ) = 10 d( 1->3 ) = 10 d( 1->4 ) = 30 d( 1->5 ) = 1000111000

Bài 2 Tìm cây khung nhỏ nhất của đồ thị bằng thuật toán Prim

Độ phức tạp: O((n+m) log n).

1

2

3

4

5

6

7

8

9

10

#include <stdio.h>

#include <vector>

#include <queue>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int, int> ii;

const int N=100005, oo=0x3c3c3c3c;

int n, m, d[N];

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

vector<int> a[N], b[N];

int prim(int u) {

int Sum = 0;

priority_queue<ii> qu;

for (int i=1; i<=n; i++) d[i]=oo;

qu.push(ii(0, u)); d[u]=0;

while (qu.size()) {

ii Pop=qu.top(); qu.pop();

int u=Pop.second, du=-Pop.first;

if (du!=d[u]) continue;

Sum+=d[u]; d[u]=0;

for (int i=0; int v=a[u][i]; i++)

if (d[v] > b[u][i]) {

d[v]=b[u][i];

qu.push(ii(-d[v], v));

}

}

return Sum;

}

main() {

scanf("%d%d", &n, &m);

for (int i=1; i<=m; i++) {

int x, y, z;

scanf("%d%d%d", &x, &y, &z);

a[x].push_back(y);

b[x].push_back(z);

a[y].push_back(x);

b[y].push_back(z);

}

for (int i=1; i<=n; i++)

a[i].push_back(0);

cout << prim(1) << endl;

}

Mô tả

1 int d[]

d[u] là khoảng cách từ nút u đến cây khung đang xây dựng, d[u]=0 khi u đã được cho vào cây khung.

2 vector<int> a[]

a[u] là danh sách kề của đỉnh u, kết thúc với số 0

3 vector<int> b[]

b[u][i] là trọng số của cạnh thứ i trong danh sách kề đỉnh u

4 int prim()

trả về trọng số của cây khung nhỏ nhất

Tham khảo

http://vn.spoj.com/problems/QBMST/

http://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_Prim

Bài 3 Robot (Đề thi chọn đội tuyển quốc gia chuyên Trần Phú Hải Phòng 2014)

HD vừa sáng tạo ra một trò chơi điều khiển robot mới cho 2 bé Bi, Bo chơi Nội dung trò chơi như sau:

- Có N cây cột đánh số từ 1 đến N, cây cột thứ 𝑖 có chiều cao ℎ[𝑖](𝑚)

- Có M đường nhảy dạng 𝑖, 𝑗, 𝑡 tương ứng là nhảy từ cây 𝑖 sang cây 𝑗 (hoặc từ cây j sang cây i) mất 𝑡(𝑠) và nếu nhảy từ độ cao ℎ (ℎ∈ Ν, ℎ ≤ ℎ[𝑖]) của cây 𝑖 thì sang cây 𝑗 sẽ có độ cao là

ℎ − 𝑡 với điều kiện 0 ≤ ℎ − 𝑡 ≤ ℎ[𝑗]

- Nếu robot di chuyển lên xuống trên cột hiện tại, thời gian di chuyển mất 1(𝑠) trên 1𝑚 di chuyển.

Hiện tại robot đang ở độ cao X của cây 1, Bi-Bo cần phải tìm phương án di chuyển nhanh nhất đếnđộ cao ℎ[𝑁] của cây N Bạn hãy giúp 2 bé Bi-Bo tính thời gian di chuyển ngắn nhất thỏa mãn yêucầu đầu bài?

Dữ liệu: Vào từ file văn bản ROBOT.INP

- Dòng 1: Chứa 3 số nguyên dương N, M, X tương ứng là số lượng cây cột, số lượng đường nhảy và độ cao của robot đang ở cột 1 (2 ≤ 𝑁 ≤ 100.000; 1 ≤

𝑀 ≤ 300.000; 0 ≤ 𝑋 ≤ℎ[1])

- N dòng tiếp theo, dòng thứ 𝑖 chứa 1 số nguyên dương ℎ[𝑖]

tương ứng là chiều cao của cột 𝑖(1 ≤ ℎ[𝑖] ≤ 1.000.000.000 ∀𝑖 =

1 𝑁).

- M dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương 𝑖, 𝑗, 𝑡

tương ứng là nhảy từ cây 𝑖 sang cây 𝑗 (hoặc từ cây 𝑗 sang cây

𝑖) mất 𝑡(𝑠) (1 ≤ 𝑡 ≤ 1.000.000.000).

Các số trên một dòng của input file được ghi cách nhau bởi dấu cách.

Kết quả: Ghi ra file văn bản ROBOT.OUT

- Ghi một số duy nhất là thời gian ngắn nhất để robot di chuyển đến độ cao ℎ[𝑁] của cây N, nếu không thể di chuyển đến thì ghi -1.

Ví dụ:

5 5 0

50

100

25

30

10

1 2 10

2 5 50

2 4 20

4 3 1

5 4 20

110 Trèo lên 50(m) ở cây 1 mất 50(s)

Nhảy từ cây 1 sang cây 2:

- Mất 10(s)

- ở ộ cao 40 trên cây 2 độ cao 40 trên cây 2 Nhảy từ cây 2 sang cây 4:

- Mất 20(s)

- ở ộ cao 20 trên cây 4 độ cao 40 trên cây 2 Nhảy từ cây 4 sang cây 5:

- Mất 20(s)

- ở ộ cao 0 độ cao 40 trên cây 2

- trèo thêm 10(m) mất 10(s) Tổng thời gian: 110(s).

2 1 0

1 1

1 2 100

-1 Từ cây 1, bất kỳ ộ cao nào, khi nhảy sang cây độ cao 40 trên cây 2

2 ều không thực hiện ược vì độ cao 40 trên cây 2 độ cao 40 trên cây 2 ℎ − 𝑡< 0.

4 3 30 100 Di chuyển xuống 10(m) ở cây 1 mất 10 (s)

10

20

50

1 2 10

2 3 10

3 4 10

và ang ở ộ cao 20(m) độ cao 40 trên cây 2 độ cao 40 trên cây 2 Nhảy sang cây 2:

- Mất 10(s)

- ở ộ cao 10 trên cây 2 độ cao 40 trên cây 2 Nhảy sang cây 3:

- Mất 10(s)

- Ở ộ cao 0(m), trèo lên 10(m) mất 10(s), độ cao 40 trên cây 2

ở ộ cao 10(m); độ cao 40 trên cây 2 Nhảy sang cây 4:

- Mất 10(s),

- ở ộ cao 0 (m), trèo lên 50(m) mất 50(s) độ cao 40 trên cây 2 Tổng thời gian: 100(s).

Chương trì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

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

#include<cstdio>

#include<queue>

#include<vector>

#include<algorithm>

using namespace std;

const int MAXN = 100005;

const long long INF = 100001000010000100ll; // >> 10^9*10^5

int H[MAXN];

long long dist[MAXN];

vector<int> to[MAXN], cost[MAXN];

struct Dat{

long long d;

int v;

Dat(long long d, int v):d(d),v(v){}

bool operator<(const Dat& a)const{ return d < a.d;}

};

int main(){

int N, M, X, A, B, T;

scanf("%d%d%d",&N,&M,&X);

for(int i = 1; i <= N; i++) scanf("%d",&H[i]);

for(int i = 0; i < M; i++){

scanf("%d%d%d",&A,&B,&T);

to[A].push_back(B);

cost[A].push_back(T);

to[B].push_back(A);

cost[B].push_back(T);

}

for(int i = 1; i <= N; i++) dist[i] = -INF;

priority_queue<Dat> q;

q.push(Dat(X,1));

while(!q.empty()){

Dat now = q.top(); q.pop();

if(dist[now.v] != -INF) continue;

dist[now.v] = now.d;

for(int i = 0; i < to[now.v].size(); i++){

int u = to[now.v][i], c = cost[now.v][i];

if(c > H[now.v]) continue;

q.push(Dat(min(now.d-c, (long long)H[u]), u));