Trong bài này, chúng ta sẽ tìm hiểu về class PriorityQueue của collections framework trong Java qua các ví dụ.
Class PriorityQueue cung cấp các hàm của cấu trúc dữ liệu đống .
Nó triển khai interface Queue .
Không giống như các queue thông thường, các phần tử trong priority queue được lấy theo thứ tự được sắp xếp.
Giả sử, chúng ta muốn lấy các phần tử theo thứ tự tăng dần. Trong trường hợp này, phần tử đầu tiên của priority queue sẽ là phần tử nhỏ nhất. Khi phần tử này được lấy đi, phần tử nhỏ nhất tiếp theo sẽ trở thanh phần tử đầu tiên của queue.
Điều quan trọng cần lưu ý là các phần tử của priority queue có thể không được sắp xếp. Tuy nhiên, chúng (các phần tử) luôn được lấy ra theo thứ tự sắp xếp.
Nội dung chính
Tạo PriorityQueue
Để tạo một priority queue, chúng ta phải nhập gói java.util.PriorityQueue. Khi chúng ta đã nhập gói, chúng ta có thể tạo priority queue trong Java theo cách dưới đây.
PriorityQueue<Integer> numbers = new PriorityQueue<>();Ở đây, chúng ta đã tạo ra một priority queue không có đối số. Trong trường hợp này, phần tử đầu của priority queue là phần tử nhỏ nhất của queue. Và các phần tử được loại bỏ khỏi queue theo thứ tự tăng dần.
Tuy nhiên, chúng ta có thể tùy chỉnh thứ tự các phần tử với Comparator interface. Chúng ta sẽ tìm hiểu về điều đó trong phần sau của bài này.
Các hàm của priority queue
Class PriorityQueue triển khai tất cả các hàm có trong Queue interface.
Chèn các phần tử vào PriorityQueue
add()- Chèn phần tử được chỉ định vào queue. Nếu queue đầy, nó sẽ ném một ngoại lệ.
offer()- Chèn phần tử được chỉ định vào queue. Nếu queue đầ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<Integer> 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);
}
}Kết quả
PriorityQueue: [2, 4]
Updated PriorityQueue: [1, 4, 2]Ở đây, chúng ta đã tạo ra một priority queue có tên là numbers. Chúng ta đã thêm phần tử 4 và 2 vào queue.
Mặc dù 4 được chèn trước 2, nhưng phần tử đầu tiên của queue lại là 2. Đó là bởi vì phần tử đầu của priority queue phải là phần tử nhỏ nhất của queue.
Sau đó chúng ta đã chèn 1 vào queue. Queue bây giờ sẽ được sắp xếp lại để lưu trữ phần tử nhỏ nhất (chính là 1) vào phần đầu của queue.
Truy cập các phần tử priority
Để truy cập các phần tử trong priority queue, chúng ta có thể sử dụng hàm peek(). Hàm này trả về phần tử đầu của queue. Ví dụ,
import java.util.PriorityQueue;
class Main {
public static void main(String[] args) {
// Creating a priority queue
PriorityQueue<Integer> 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);
}
}
Kết quả
PriorityQueue: [1, 4, 2]
Accessed Element: 1Xóa các phần tử khỏi priority queue
remove() – xóa phần tử đã chỉ định khỏi queue
poll() – trả về và loại bỏ phần tử đầu của queue
Ví dụ,
import java.util.PriorityQueue;
class Main {
public static void main(String[] args) {
// Creating a priority queue
PriorityQueue<Integer> 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);
}
}Kết quả
PriorityQueue: [1, 4, 2]
Is the element 2 removed? true
Removed Element Using poll(): 1Thực hiện việc lặp với priorityQueue
Để lặp lại các phần tử của priority queue, chúng ta có thể sử dụng hàm iterator(). Để sử dụng hàm này, chúng ta phải nhập gói java.util.Iterator. Ví dụ,
import java.util.PriorityQueue;
import java.util.Iterator;
class Main {
public static void main(String[] args) {
// Creating a priority queue
PriorityQueue<Integer> numbers = new PriorityQueue<>();
numbers.add(4);
numbers.add(2);
numbers.add(1);
System.out.print("PriorityQueue using iterator(): ");
//Using the iterator() method
Iterator<Integer> iterate = numbers.iterator();
while(iterate.hasNext()) {
System.out.print(iterate.next());
System.out.print(", ");
}
}
}
Kết quả
PriorityQueue using iterator(): 1, 4, 2,Các hàm khác trong priority queue:
| Hàm | Mô tả |
| contains(element) | Tìm kiếm một phần tử được chỉ định trong priority queue. Nếu phần tử được tìm thấy, hàm này trả về true, nếu không thì nó trả về false. |
| size() | Trả về độ dài của priority queue. |
| toArray() | Chuyển đổi một priority queue thành một mảng và trả về nó. |
Mạch so sánh priority
Trong tất cả các ví dụ trên, các phần tử priority queue được truy xuất theo thứ tự tự nhiên (thứ tự tăng dần). Tuy nhiên, chúng ta có thể tùy chỉnh thứ tự này.
Để làm được điều này, chúng ta cần tạo class comparator riêng, class này triển khai Comparator interface. Ví dụ,
import java.util.PriorityQueue;
import java.util.Comparator;
class Main {
public static void main(String[] args) {
// Creating a priority queue
PriorityQueue<Integer> 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<Integer> {
@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;
}
}
}Kết quả
PriorityQueue: [4, 3, 1, 2]Trong ví dụ trên, chúng ta đã tạo một priority queue vượt qua class CustomComparator làm đối số.
Class CustomComparator triển khai Comparator interface.
Chúng tôi sau đó ghi đè lên hàm compare(). Lúc này, hàm này sẽ làm cho phần tử đầu là số lớn nhất.
Để tìm hiểu thêm về mạch so sánh, hãy truy cập Trình Mạch so sánh trong Java .
