Trong hướng dẫn này, chúng ta sẽ tìm hiểu về lớp PriorityQueue của khung công tác bộ sưu tập Java với sự trợ giúp của các ví dụ.
Các PriorityQueuelớp học cung cấp các chức năng của cấu trúc dữ liệu heap.
Nó thực hiện giao diện Hàng đợi.
Không giống như các hàng đợi thông thường, các phần tử của hàng đợi ưu tiên được truy xuất theo thứ tự đã được sắp xếp.
Giả sử, chúng ta muốn truy xuất các phần tử theo thứ tự tăng dần. Trong trường hợp này, phần đầu của hàng đợi ưu tiên sẽ là phần tử nhỏ nhất. Khi phần tử này được truy xuất, phần tử nhỏ nhất tiếp theo sẽ là phần đầu của hàng đợi.
Điều quan trọng cần lưu ý là các phần tử của hàng đợi ưu tiên có thể không được sắp xếp. Tuy nhiên, các phần tử luôn được truy xuất theo thứ tự được sắp xếp.
Tạo PriorityQueue
Để tạo hàng đợi ưu tiên, chúng ta phải nhập java.util.PriorityQueuegói. Sau khi chúng tôi nhập gói, đây là cách chúng tôi có thể tạo một hàng đợi ưu tiên trong Java.
PriorityQueue numbers = new PriorityQueue();
Ở đây, chúng tôi đã tạo một hàng đợi ưu tiên mà không có bất kỳ đối số nào. Trong trường hợp này, phần đầu của hàng đợi ưu tiên là phần tử nhỏ nhất của hàng đợi. Và các phần tử được loại bỏ theo thứ tự tăng dần khỏi hàng đợi.
Tuy nhiên, chúng ta có thể tùy chỉnh thứ tự của các phần tử với sự trợ giúp của Comparatorgiao diện. Chúng ta sẽ tìm hiểu về điều đó sau trong hướng dẫn này.
Phương thức ưu tiên
Các PriorityQueuelớp học cung cấp cho việc thực hiện tất cả các phương pháp hiện diện trong Queuegiao diện.
Chèn các phần tử vào PriorityQueue
add()- Chèn phần tử được chỉ định vào hàng đợi. Nếu hàng đợi đã đầy, nó sẽ ném ra một ngoại lệ.offer()- Chèn phần tử được chỉ định vào hàng đợi. Nếu hàng đợi đã đầy, nó sẽ trả vềfalse.
Ví dụ,
import java.util.PriorityQueue; class Main ( public static void main(String() args) ( // Creating a priority queue PriorityQueue numbers = new PriorityQueue(); // Using the add() method numbers.add(4); numbers.add(2); System.out.println("PriorityQueue: " + numbers); // Using the offer() method numbers.offer(1); System.out.println("Updated PriorityQueue: " + numbers); ) )
Đầu ra
PriorityQueue: (2, 4) Đã cập nhật PriorityQueue: (1, 4, 2)
Ở đây, chúng tôi đã tạo một hàng đợi ưu tiên có tên là số. Chúng tôi đã chèn 4 và 2 vào hàng đợi.
Mặc dù 4 được chèn trước 2, phần đầu của hàng đợi là 2. Đó là vì phần đầu của hàng đợi ưu tiên là phần tử nhỏ nhất của hàng đợi.
Sau đó, chúng tôi đã chèn 1 vào hàng đợi. Hàng đợi bây giờ được sắp xếp lại để lưu phần tử nhỏ nhất 1 vào phần đầu của hàng đợi.
Truy cập phần tử giá trị ưu tiên
Để truy cập các phần tử từ hàng đợi ưu tiên, chúng ta có thể sử dụng peek()phương pháp. Phương thức này trả về phần đầu của hàng đợi. Ví dụ,
import java.util.PriorityQueue; class Main ( public static void main(String() args) ( // Creating a priority queue PriorityQueue numbers = new PriorityQueue(); numbers.add(4); numbers.add(2); numbers.add(1); System.out.println("PriorityQueue: " + numbers); // Using the peek() method int number = numbers.peek(); System.out.println("Accessed Element: " + number); ) )
Đầu ra
PriorityQueue: (1, 4, 2) Phần tử được truy cập: 1
Xóa phần tử PriorityQueue
remove()- loại bỏ phần tử được chỉ định khỏi hàng đợipoll()- trả về và loại bỏ phần đầu của hàng đợi
Ví dụ,
import java.util.PriorityQueue; class Main ( public static void main(String() args) ( // Creating a priority queue PriorityQueue numbers = new PriorityQueue(); numbers.add(4); numbers.add(2); numbers.add(1); System.out.println("PriorityQueue: " + numbers); // Using the remove() method boolean result = numbers.remove(2); System.out.println("Is the element 2 removed? " + result); // Using the poll() method int number = numbers.poll(); System.out.println("Removed Element Using poll(): " + number); ) )
Đầu ra
PriorityQueue: (1, 4, 2) Phần tử 2 có bị loại bỏ không? true Phần tử đã Loại bỏ Sử dụng thăm dò ý kiến (): 1
Lặp lại trên một giá trị ưu tiên
Để lặp lại các phần tử của hàng đợi ưu tiên, chúng ta có thể sử dụng iterator()phương thức này. Để sử dụng phương pháp này, chúng ta phải nhập java.util.Iteratorgói. Ví dụ,
import java.util.PriorityQueue; import java.util.Iterator; class Main ( public static void main(String() args) ( // Creating a priority queue PriorityQueue numbers = new PriorityQueue(); numbers.add(4); numbers.add(2); numbers.add(1); System.out.print("PriorityQueue using iterator(): "); //Using the iterator() method Iterator iterate = numbers.iterator(); while(iterate.hasNext()) ( System.out.print(iterate.next()); System.out.print(", "); ) ) )
Đầu ra
PriorityQueue sử dụng biến lặp (): 1, 4, 2,
Các phương thức ưu tiên khác
| Phương pháp | Mô tả |
|---|---|
contains(element) | Tìm kiếm hàng đợi ưu tiên cho phần tử được chỉ định. Nếu phần tử được tìm thấy, nó sẽ trả về true, nếu không nó sẽ trả về false. |
size() | Trả về độ dài của hàng đợi ưu tiên. |
toArray() | Chuyển đổi một hàng đợi ưu tiên thành một mảng và trả về nó. |
Bộ so sánh giá trị ưu tiên
Trong tất cả các ví dụ trên, các phần tử hàng đợi ưu tiên được truy xuất theo thứ tự tự nhiên (thứ tự tăng dần). Tuy nhiên, chúng tôi có thể tùy chỉnh thứ tự này.
Đối với điều này, chúng ta cần tạo lớp so sánh của riêng mình để triển khai Comparatorgiao diện. Ví dụ,
import java.util.PriorityQueue; import java.util.Comparator; class Main ( public static void main(String() args) ( // Creating a priority queue PriorityQueue numbers = new PriorityQueue(new CustomComparator()); numbers.add(4); numbers.add(2); numbers.add(1); numbers.add(3); System.out.print("PriorityQueue: " + numbers); ) ) class CustomComparator implements Comparator ( @Override public int compare(Integer number1, Integer number2) ( int value = number1.compareTo(number2); // elements are sorted in reverse order if (value> 0) ( return -1; ) else if (value < 0) ( return 1; ) else ( return 0; ) ) )
Đầu ra
PriorityQueue: (4, 3, 1, 2)
Trong ví dụ trên, chúng ta đã tạo một hàng đợi ưu tiên chuyển lớp CustomComparator làm đối số.
Lớp CustomComparator thực hiện Comparatorgiao diện.
Sau đó, chúng tôi ghi đè compare()phương thức. Phương thức bây giờ làm cho phần đầu của phần tử là số lớn nhất.
Để tìm hiểu thêm về trình so sánh, hãy truy cập Trình so sánh Java.
