Chào ace, bài bác này bọn họ sẽ tìm hiểu về Priority Q ueue – Hàng hóng ưu tiên vào series tự học về cấu tạo dữ liệu(CTDL) với giải thuật, dưới đây cafedev sẽ reviews và share chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các phần sau.

Bạn đang xem: Hàng đợi ưu tiên c++

Priority Queue – Hàng hóng ưu tiên là một chiến thuật mở rộng của Queue – sản phẩm đợi, với các thuộc tính sau:

– Mọi thành phần đều được nối sát với một độ ưu tiên

– một trong những phần tử tất cả độ ưu tiên cao sẽ tiến hành dequeued (xóa ngoài Priority Queue) trước một trong những phần tử tất cả độ ưu tiên thấp

– trường hợp hai phần tử có cùng độ ưu tiên, bây giờ việc thành phần nào được cách xử lý trước sẽ phụ thuộc vào vào đồ vật tự của chúng ở vào Priority Queue.


Trong Priority Queue dưới đây, phần tử có giá trị ASCII béo nhất sẽ có độ ưu tiên cao nhất.

*

Một Priority Queue điển hình/thông hay sẽ hỗ trợ các thao tác làm việc xử lý tài liệu sau:

– insert(item, priority): Chèn thêm một phần tử cùng với độ ưu tiên nạm thể

– get
Highest
Priority(): Trả về thành phần có độ ưu tiên cao nhất

– delete
Highest
Priority(): Xóa đi/loại vứt đi phần tử có độ ưu tiên cao nhất.


Nội dung chính


1. Cách thiết đặt Priority Queue – Hàng hóng ưu tiên

1. Thiết đặt Priority Queue bằng Array – Mảng một chiều

Có thể setup Priority Queue dễ dàng và đơn giản bằng một mảng một chiều chứa các thành phần có cấu tạo giống như struct sau đây:

struct tòa tháp

int item;

int priority;

– thao tác insert() rất có thể được tải đặt bằng cách chèn thêm một trong những phần tử vào thời điểm cuối mảng vào khoảng thời gian là O(1).

– get
Highest
Priority() hoàn toàn có thể được cài đặt đặt bằng phương pháp tìm kiếm con đường tính thành phần có độ ưu tiên cao nhất trong mảng. Làm việc này tốn O(n) thời gian.

– delete
Highest
Priority() hoàn toàn có thể được download đặt bằng cách đầu tiên tìm kiếm tuyến đường tính thành phần có độ ưu tiên cao nhất trong mảng, kế tiếp loại bỏ phần tử ấy thoát ra khỏi mảng bằng cách di chuyển tất cả các thành phần nằm sau nó lùi lại một đơn vị chức năng vị trí.


Chúng ta cũng hoàn toàn có thể sử dụng Linked list để cài đặt Priority Queue, độ phức hợp về thời hạn của tất cả các phép xử lý tài liệu với Linked các mục vẫn sẽ giống như khi cần sử dụng mảng một chiều. điểm mạnh của việc thực hiện Linked danh mục đó là hàm delete
Highest
Priority() có thể sẽ tác dụng hơn vì họ không cần phải di chuyển lùi lại các phần tử nữa.

2. Sử dụng Heaps

Cấu trúc tài liệu Heap thường xuyên được ưu tiên áp dụng để setup Priority Queue chính vì Heap cung ứng hiệu năng tốt hơn khi so với mảng tuyệt Linked List.

– trong một Binary Heap, hàm get
Highest
Priority() rất có thể được cài đặt để có độ tinh vi thời gian là O(1), hàm insert() rất có thể được cài đặt với độ tinh vi thời gian là O(Logn) với hàm delete
Highest
Priority() cũng hoàn toàn có thể được setup để tất cả độ tinh vi thời gian là O(Logn).

– cùng với Fibonacci Heap, hàm insert() và hàm get
Highest
Priority() rất có thể được cài đặt với độ phức hợp về thời gian là O(1), và hàm delete
Highest
Priority() hoàn toàn có thể được thiết lập với độ phức hợp về thời gian là O(Logn).

3. Các ứng dụng của Priority Queue

1. Lập lịch CPU

2. Các Grapth algorithms – thuật toán Đồ thị như thuật toán tìm lối đi ngắn độc nhất vô nhị Dijkstra, thuật toán Prim tìm kiếm cây khung bé dại nhất, v.v…

3. Tất cả các vận dụng xếp sản phẩm có liên quan đến cường độ ưu tiên.

Nguồn với Tài liệu tiếng anh tham khảo:

Tài liệu từ cafedev:

Nếu chúng ta thấy hay và hữu ích, chúng ta có thể tham gia những kênh sau của cafedev nhằm nhận được rất nhiều hơn nữa:

Mở đầu Mở đầu Hàng đợi ưu tiên Hàng đợi ưu tiên Heap giới thiệu về Heap, max heap Min Heap bố trí heap sort Bảng băm - Hash table Bảng băm - Hash table giải quyết xung bỗng dưng - Separate chaining

Trong bài này chúng ta sẽ cùng nhau tìm hiểu về hàng đợi ưu tiên.

Nếu bạn đã đọc qua loạt bài học về cấu trúc dữ liệu vun đống - heap, thì bạn sẽ biết hàng đợi ưu tiên là một ứng dụng của heap.

Tuy nhiên bạn có thể thực hiện hàng đợi ưu tiên mà không cần dùng heap. Nhưng lại dùng heap để xây dựng hàng đợi ưu tiên là cách hiệu quả, tối ưu và giỏi được dùng nhất.

Trong một số ngôn ngữ như C++ thì hàng đợi ưu tiên đã được mang lại vào trong bộ thư viện chuẩn và ta chỉ việc gọi ra để dùng,các bạn có thể tham khảo ở đây. Mặc dù trong rất nhiều các trường hợp khác ta phải tự tay xây dựng hàng đợi ưu tiên và cải tiến nó để giải quyết được các bài toán phức tạp hơn.

Định nghĩa hàng đợi ưu tiên

Hàng đợi ưu tiên cũng có những tính chất giống như hàng đợi đó là chèn phần tử vào phía cuối và lấy ra từ phía đầu. Nhưng có điểm khác đó là thứ tự các phần tử vào hàng đợi ưu tiên phụ thuộc vào dộ ưu tiên của phần tử đó.còn hàng đợi bình thường thì tuân theo tính chất FIFO (vào trước ra trước).

Phần tử với độ ưu tiên cao nhất sẽ được xếp lên đầu hàng đợi và phần tử với độ ưu tiên thấp nhất sẽ được chuyển xuống cuối.

Do vạy, khi bạn chèn một phần tử vào cuối hàng đợi ưu tiên, no có thể được chuyển lên đầu tiên nếu độ ưu tiên của nó là cao nhất.

Ví dụ về hàng đợi ưu tiên

Giả sử ta có một mảng với 5 phần tử: 4, 8, 1, 7, 3 và bạn phải chèn các phần tử này vào một hàng đợi ưu tiên theo giá trị lớn nhất.

Bước 1: Ban đầu hàng đợi rỗng, vì chưng vậy 4 được chèn vào.

Bước 2: Chèn 8 vào hàng đợi, vì chưng 8 lớn rộng 4 lên 8 được đẩy lên đầu hàng đợi.

Bước 3: chèn 1 vào hàng đợi, 1 nhỏ hơn 4 và 8 buộc phải 1 giữ nguyên vị trí ở cuối hàng đợi.

Bước 4: Chèn 7 vào hàng đợi, 7 lớn rộng 1 và 4, nhỏ hơn 8 nên 7 được đẩy lên vị trí nằm giữa 4 và 8.

Bước 5: Chèn 3 vào hàng đợi, 3 lớn rộng 1 và nhỏ hơn 4 lên 3 được đẩy lên vị trí nằm giữa 1 và 4.

Tất cả các bước được mô tả dưới hình sau:

*

Hình 1: mô tả hoạt động của hàng đợi ưu tiên

Có nhiều cách để xây dựng hàng đợi ưu tiên.

Cách tiếp cận đối kháng giản

Giả sử ta có N phần tử và phải chèn chúng vào hàng đợi ưu tiên. Chúng ta có thể sử dụng danh sách liên kết để thực hiện chèn các phần tử với độ phức tạp O(N) (trong trường hợp ta chèn phần tử vào cuối danh sách liên kết)và có thể sắp xếp lại chúng để duy trì các đặc tính của hàng đợi ưu tiên với độ phức tạp O(Nlog
N).

Cách tiếp cận tối ưu

Sử dụng heap để xây dựng hàng đợi ưu tiên với độ phức tạp là O(log
N) mang đến việc chèn và xóa phần tử khỏi hàng đợi.

Dựa vào cấu trúc heap, hàng đợi ưu tiên cũng chia nhỏ ra làm nhị loại là hàng đợi ưu tiên theo giá trị lớn nhất (max -priority queue) và hàng đợi ưu tiên theo giá trị nhỏ nhất (min - priority queue).

Trong phạm vi bài học này chúng ta sẽ đi sâu vào tìm hiểu hàng đợi ưu tiên theo giá trị lớn nhất. Cách xây dựng hàng đợi ưu tiên theo giá trị nhỏ nhất cũng tương tự như vậy.

Hàng đợi ưu tiên theo giá trị lớn nhất có thể thực hiện các thao tác sau:

Trả về phần tử lớn nhất trong hàng đợi ưu tiên.Xóa phần tử có giá trị lớn nhất ra khỏi hàng đợi ưu tiên và trả về giá trị của nó.Chèn phần tử vào hàng đợi ưu tiên.Cài đặt hàng đợi ưu tiên - priority queue

Ta cùng xét cách viết các hàm thực hiện các thao tác vào hàng đợi ưu tiên.

Giả sử ta có A là mảng để lưu lại các phần tử của hàng đợi ưu tiên.

N là số phần tử hiện có trong hàng đợi.

Hàm chèn phần tử vào hàng đợi ưu tiên:

Khi chèn phần tử vào hàng đợi, nó có thể vi phạm các quy tắc của max heap, nếu vậy ta phải thực hiện đổi chỗ giá trị node phụ vương và của node đó đến tới khi ta có được giá trị của node cha là lớn hơn.

void insert_element(int A< >, int val){ N = N + 1; /* Tăng kích thước của hàng đợi lên 1 khi ta chèn thêm phần tử vào */ int i = N; /* N là biến toàn cục, tránh việc thay đổi giá trị của nó, ta sử dụng biến tạm i ở đây, để có thể tùy ý xử lý */ A< i > = val; /* Trước tiên phần tử được chèn vào vị trí cuối cùng của hàng đợi */ while( i > 1 and A< i/2 > Độ phức tạp về thời gian: O(log
N)

Hàm trả về giá trị lớn nhất trong hàng đợi:

int max_element(int A< >) return A<1>; /* A<1> là node gốc trong max heap và node gốc vào max heap là node có giá trị lớn nhất */Độ phức tạp thời gian: O(1)

Hàm xóa phần tử lớn nhất ra khỏi hàng đợi ưu tiên và trả về giá trị của nó:

int pop_max_element (int A< >){ if(N == 0) { cout
Độ phức hợp thời gian: O(log
N).

Ví dụ về các thao tác với hàng đợi ưu tiên

Gỉa sử ban sơ ta có 5 thành phần trong hàng hóng ưu tiên như sau: 8,7,4,3,1

Ta xét chuỗi các thao tác sau:

Chèn phần tử mới vào hàng đợi ưu tiên

insert_element(A, 6). Lúc chèn 6 vào hàng đợi trên, các quy tắc của hàng đợi ưu tiên bị vi phạm (vi phạm luật lệ của max heap). Thế nên ta phải tiến hành đổi nơi với node chacủa nó, node có mức giá trị 4. Sau khoản thời gian đổi chỗ, những quy tắc của max heap được duy trì. Cùng xem hình biểu lộ dưới đây.

*

Hình 2: Chèn thành phần vào hàng đợi ưu tiên

Xóa phần tử lớn duy nhất khỏi hàng chờ và trả về giá trị của nó

pop_max_element() sẽ lấy thành phần có giá chỉ trị lớn nhất ra khỏi hàng chờ (node nơi bắt đầu của max heap).

Như sống hình bên dưới đây bộ phận có quý hiếm 8 sẽ tiến hành lấy ra, và thành phần cuối thuộc trong hàng đợi có mức giá trị 4 sẽ được chuyển lên nắm chỗ của bộ phận vừa được lấy ra. Từ bây giờ các quy tác của max heap bị phá vỡ yêu cầu ta cần thực hiện hàm max_heap() để gia hạn lại các quy tắc này.

*

Hình 3: Xóa thành phần lớn tuyệt nhất khỏi hàng đợi ưu tiên theo giá bán trị to nhất

Mã nguồn tương đối đầy đủ của chương trình setup hàng ngóng ưu tiên

#includeusing namespace std;int N;void insert_element(int A< >, int val) N = N + 1; /* Tăng kích thước của hàng đợi lên 1 khi ta chèn thêm phần tử vào */ int i = N; /* N là biến toàn cục, không nên thay đổi giá trị của nó, ta sử dụng biến tạm i ở đây, để có thể tùy ý xử lý */ A< i > = val; /* Trước tiên phần tử được chèn vào vị trí cuối cùng của hàng đợi */ while( i > 1 & A< i/2 > A ) /* N là số bộ phận trong mảng, biến toàn thể */ largest = left; else largest = i; if(right A ) largest = right; if(largest != i ) swap (A , A); max_heap (A, largest); int max_element(int A< >) return A<1>; /* A<1> là node gốc trong max heap và node gốc trong max heap là node có giá trị lớn nhất */int pop_max_element (int A< >){ if(N == 0) { cout tác dụng chương trình sau khi chạy và kiểm soát tại https://www.onlinegdb.com.

*

Source code trên gitlab: https://gitlab.com/thevngeek/basic-data-structure/blob/master/hangdoiuutien.cpp

Ta có thể thấy cùng với cách triển khai như trên các phần tử của hàng ngóng ưu tiên mặc dù không luôn luôn luôn bố trí theo đúng trang bị tự mập trước, bé nhỏ sau. Nhưng những lần lấy thành phần ra ngoài hàng chờ ta luôn luôn được bảo vệ rằng bộ phận đó là bự nhất, vì thế quy tắc bộ phận có độ ưu tiên cao hơn sẽ được ra khỏi hàng đợi trước (được phục vụ trước) vẫn được duy trì đúng. Và ưu thế của bí quyết làm này mang đến ta lợi về tốc độ chạy chương trình.

Xem thêm: Ai Nói Tui Yêu Anh Tập 12 - Chức Vụ Cung Ứng Lời Tập 25 Số 4 Kì 2: Nckt Giô

Như vậy ta rất có thể ứng dụng hàng đợi ưu tiên nhằm lập lịch công việc. Khi ta bao gồm một hàng đợi với N công việc, mỗi công việc đều gồm độ ưu tiên của riêng rẽ nó. Nếu quá trình có độ ưu tiên tối đa sẽ được xong trước và xóa sổ khỏi mặt hàng đợi, ta có thể dùng hàm pop_max_element() để triển khai việc này. Và nếu trên mỗi thời điểm ta buộc phải thêm một các bước mới vào mặt hàng đợi, ta hoàn toàn có thể dùng hàm insert_element() để thêm bộ phận với độ phức tạp về thời gian là O(log
N) và gia hạn các quy tắc của max heap (node thân phụ luôn luôn luôn có giá chỉ trị to hơn các node con).

Tham khảo

1.https://vi.wikipedia.org/wiki/%C4%90%E1%BB%91ng_nh%E1%BB%8B_ph%C3%A2n

2.https://www.hackerearth.com/practice/data-structures/trees/heapspriority-queues/tutorial/