Priority queue là gì

Chào ace, bài bác này chúng ta vẫn tìm hiểu về Priority Q ueue – Hàng hóng ưu tiên trong series trường đoản cú học về kết cấu dữ liệu(CTDL) và lời giải, tiếp sau đây opdaichien.com đã trình làng và share chi tiết(có mang, độ phức hợp, ứng dụng của nó, code ví dụ…) về nó trải qua các phần sau.

Bạn đang xem: Priority queue là gì

Priority Queue – Hàng ngóng ưu tiên là một trong những chiến thuật mở rộng của Queue – Hàng chờ, với những trực thuộc tính sau:

– Mọi phần tử đông đảo được nối sát với cùng 1 độ ưu tiên

– Một thành phần bao gồm độ ưu tiên cao sẽ tiến hành dequeued (xóa khỏi Priority Queue) trước 1 phần tử bao gồm độ ưu tiên thấp

– Nếu hai phần tử bao gồm cùng độ ưu tiên, hôm nay bài toán phần tử nào được cách xử lý trước đã dựa vào vào lắp thêm trường đoản cú của chúng ngơi nghỉ trong Priority Queue.


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

*

Một Priority Queue điển hình/thường thì đang cung cấp những thao tác cách xử lý dữ liệu sau:

– insert(cống phẩm, priority): Ckém thêm một phần tử với độ ưu tiên chũm thể

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

– deleteHighestPriority(): Xóa đi/sa thải đi thành phần tất cả độ ưu tiên tối đa.


Nội dung chính


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

1. Cài đặt Priority Queue bằng Array – Mảng một chiều

Có thể thiết đặt Priority Queue đơn giản và dễ dàng bằng một mảng một chiều đựng các phần tử có kết cấu y hệt như struct sau đây:

struct chiến thắng

int item;

int priority;

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

– getHighestPriority() rất có thể được cài đặt bằng cách tìm kiếm con đường tính phần tử bao gồm độ ưu tiên tối đa trong mảng. Thao tác này tốn O(n) thời hạn.

Xem thêm: Sale Off Là Gì ? Phân Biệt Sale Off Và Sale Up To Thế Nào Mới Đúng

– deleteHighestPriority() có thể được thiết đặt bằng phương pháp thứ nhất tìm kiếm con đường tính bộ phận gồm độ ưu tiên cao nhất trong mảng, tiếp đến sa thải bộ phận ấy ra khỏi mảng bằng phương pháp dịch rời tất cả các phần tử nằm sau nó lùi lại một đơn vị vị trí.


Chúng ta cũng rất có thể áp dụng Linked List để thiết đặt Priority Queue, độ tinh vi về thời gian của tất cả các phép giải pháp xử lý dữ liệu với Linked List vẫn đã y như khi sử dụng mảng một chiều. Lợi cầm cố của bài toán thực hiện Linked List chính là hàm deleteHighestPriority() có thể sẽ tác dụng hơn vị họ không cần phải di chuyển lùi lại những thành phần nữa.

2. Sử dụng Heaps

Cấu trúc dữ liệu Heap thường được ưu tiên sử dụng để thiết đặt Priority Queue cũng chính vì Heap cung ứng hiệu năng tốt hơn Khi đối với mảng tuyệt Linked List.

– Trong một Binary Heap, hàm getHighestPriority() hoàn toàn có thể được thiết lập để sở hữu độ tinh vi thời gian là O(1), hàm insert() có thể được thiết lập cùng với độ tinh vi thời gian là O(Logn) với hàm deleteHighestPriority() cũng hoàn toàn có thể được thiết lập để sở hữu độ phức tạp thời gian là O(Logn).

– Với Fibonacci Heap, hàm insert() cùng hàm getHighestPriority() có thể được thiết đặt cùng với độ tinh vi về thời hạn là O(1), cùng hàm deleteHighestPriority() rất có thể được setup với độ phức tạp về thời hạn là O(Logn).

Xem thêm: Vì Sao Cá Sủ Vàng Lại Đắt Như Vậy? Vì Sao Cá Sủ Vàng Đắt Như Vàng

3. Các vận dụng của Priority Queue

1. Lập lịch CPU

2. Các Grapth algorithms – thuật toán Đồ thị nlỗi thuật tân oán search đường đi ngắn độc nhất vô nhị Dijkstra, thuật toán Prlặng tìm cây size nhỏ tuổi tốt nhất, v.v…

3. Tất cả các ứng dụng xếp hàng bao gồm tương quan đến hơn cả độ ưu tiên.

Nguồn với Tài liệu giờ anh tsay mê khảo:

Tài liệu từ opdaichien.com:

Nếu bạn thấy tốt cùng bổ ích, bạn cũng có thể tmê mệt gia các kênh sau của opdaichien.com để nhấn được không ít rộng nữa:


Chuyên mục: Kiến Thức