Hàng đợi ưu tiên Java: không phải hàng đợi cổ điển

Trong bài viết này, chúng ta tìm hiểu một hàng đợi ưu tiên, lớp Java, triển khai giao diện Queue. Lập trình viên biết gì về Giao diện hàng đợi thông thường? Trước hết, giao diện này dựa trên nguyên tắc FIFO hay “vào trước ra trước”. Điều đó nhắc nhở một hàng đợi thông thường theo nghĩa thông thường của nó. Bạn muốn lấy cà phê từ McDrive? Nếu ô tô của bạn là người đầu tiên ở gần cửa sổ, bạn sẽ lấy cà phê trước người lái xe tiếp theo.

Khai báo giao diện hàng đợi

public interface Queue<E> extends Collection<E>

Hàng đợi ưu tiên là gì

Hàng đợi ưu tiên là gì? Trước hết, nó là một lớp cài đặt giao diện Hàng đợi trong trường hợp chèn một phần tử từ phía sau và loại bỏ một phần tử từ đầu. Tuy nhiên nó không phải là một hàng đợi thông thường bên trong. Thứ tự của các phần tử hàng đợi ưu tiên Java phụ thuộc vào mức độ ưu tiên của các phần tử. Phần tử có mức ưu tiên cao nhất sẽ được chuyển lên đầu hàng đợi. Nếu bạn xóa (phục vụ) phần tử được xếp hạng cao nhất, phần tử thứ hai sẽ đi đến phần đầu để lấy cà phê. Ưu tiên được xác định như thế nào? Theo tài liệu, các phần tử của hàng đợi ưu tiên được sắp xếp theo thứ tự tự nhiên của chúng hoặc theo Bộ so sánh được cung cấp tại thời điểm xây dựng hàng đợi, tùy thuộc vào hàm tạo nào được sử dụng. Một hàng đợi ưu tiên dựa trên một đống tối thiểu ưu tiên. Điều đó có nghĩa là, trong trường hợp các phần tử hàng đợi số, phần tử đầu tiên của hàng đợi sẽ là phần tử nhỏ nhất trong số này. Khá thường xuyên sau khi đọc định nghĩa này, sinh viên tân binh bắt đầu nghĩ rằng hàng đợi ưu tiên được sắp xếp theo nghĩa tuyến tính. Đó là, giả sử, nếu chúng ta sử dụng một hàng đợi có các phần tử là số tự nhiên, thì phần tử đầu tiên sẽ là phần tử nhỏ nhất và phần tử cuối cùng sẽ là phần tử lớn nhất. Điều này không hoàn toàn đúng. Để hiểu hàng đợi ưu tiên thực sự hoạt động như thế nào và nó mang lại những gì, bạn cần tìm ra cách thức hoạt động của heap. Chúng ta xem xét cấu trúc bên trong của hàng đợi ưu tiên bằng một ví dụ sau. Bây giờ hãy tập trung vào các thuộc tính bên ngoài của nó. thì phần tử đầu tiên sẽ là phần tử nhỏ nhất và phần tử cuối cùng - phần tử lớn nhất. Điều này không hoàn toàn đúng. Để hiểu hàng đợi ưu tiên thực sự hoạt động như thế nào và nó mang lại những gì, bạn cần tìm ra cách thức hoạt động của heap. Chúng ta xem xét cấu trúc bên trong của hàng đợi ưu tiên bằng một ví dụ sau. Bây giờ hãy tập trung vào các thuộc tính bên ngoài của nó. thì phần tử đầu tiên sẽ là phần tử nhỏ nhất và phần tử cuối cùng - phần tử lớn nhất. Điều này không hoàn toàn đúng. Để hiểu hàng đợi ưu tiên thực sự hoạt động như thế nào và nó mang lại những gì, bạn cần tìm ra cách thức hoạt động của heap. Chúng ta xem xét cấu trúc bên trong của hàng đợi ưu tiên bằng một ví dụ sau. Bây giờ hãy tập trung vào các thuộc tính bên ngoài của nó.

Khai báo và khởi tạo lớp PriorityQueue

Lớp PriorityQueue cung cấp 6 cách khác nhau để xây dựng hàng đợi ưu tiên trong Java.

• PriorityQueue() - hàng đợi trống với dung lượng ban đầu mặc định (11) sắp xếp các phần tử của nó theo thứ tự tự nhiên của chúng.
• PriorityQueue(Collection c) - hàng đợi trống chứa các phần tử trong bộ sưu tập đã chỉ định.
• PriorityQueue(int initCapacity) - hàng đợi trống với dung lượng ban đầu được chỉ định sắp xếp các phần tử của nó theo thứ tự tự nhiên của chúng.
• PriorityQueue(int initCapacity, Bộ so sánh bộ so sánh) - hàng đợi trống với dung lượng ban đầu đã chỉ định sắp xếp các phần tử của nó theo bộ so sánh đã chỉ định.
• PriorityQueue(PriorityQueue c) - hàng đợi trống chứa các phần tử trong hàng đợi ưu tiên đã chỉ định.
• PriorityQueue(SortedSet c) - hàng đợi trống chứa các phần tử trong tập hợp được sắp xếp đã chỉ định.

Hàng đợi ưu tiên trong Java được khai báo theo cách tiếp theo:

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

Tạo hàng đợi ưu tiên

Hãy tạo một hàng đợi ưu tiên của các số nguyên. Triển khai hàng đợi ưu tiên, mã Java:

PriorityQueue<Integer> numbers = new PriorityQueue<>();

Chúng tôi đã tạo hàng đợi ưu tiên không có đối số. Trong trường hợp này, người đứng đầu hàng đợi ưu tiên là số tối thiểu của hàng đợi. Nếu bạn loại bỏ phần đầu, phần tử nhỏ nhất tiếp theo sẽ chiếm vị trí này. Vì vậy, bạn có thể xóa các phần tử khỏi hàng đợi theo thứ tự tăng dần. Nếu cần, bạn có thể thay đổi nguyên tắc đặt hàng bằng giao diện Bộ so sánh.

Các phương thức PriorityQueue của Java

Lớp PriorityQueue Java có các phương thức quan trọng để thêm, xóa và kiểm tra các phần tử.

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

• boolean add(object) chèn phần tử đã chỉ định vào hàng đợi ưu tiên. Trả về true trong trường hợp thành công. Nếu hàng đợi đầy, phương thức sẽ đưa ra một ngoại lệ.
• boolean offer(object) chèn phần tử đã chỉ định vào hàng đợi ưu tiên này. Nếu hàng đợi đầy, phương thức trả về false.

Bạn có thể sử dụng cả hai thao tác thêm, không có sự khác biệt nào đối với đa số các trường hợp. Dưới đây là một ví dụ nhỏ về khởi tạo và thêm các phần tử vào hàng đợi ưu tiên.

import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        for (int i = 5; i > 0; i--) {
            priorityQueue1.add(i);
        }
        System.out.println(priorityQueue1);
    priorityQueue1.offer(0);
        System.out.println(priorityQueue1);
    }
}

Đầu ra là:

[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]

Thứ tự của các phần tử có vẻ hơi lạ, chúng tôi sẽ giải thích sau.

Truy xuất và xóa các phần tử khỏi Hàng đợi ưu tiên

• boolean remove(object) xóa một phiên bản duy nhất của phần tử đã chỉ định khỏi hàng đợi này, nếu nó hiện diện.
• Object poll() truy xuất và loại bỏ phần đầu của hàng đợi này. Trả về null nếu hàng đợi trống.
• void clear() xóa tất cả các phần tử khỏi hàng đợi ưu tiên.
• Phần tử đối tượng() truy xuất phần đầu của hàng đợi này mà không xóa nó. Ném NoSuchElementException nếu hàng đợi trống.
• Đối tượng peek() truy xuất phần đầu của hàng đợi mà không xóa nó. Trả về null nếu hàng đợi trống.

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //put 5 elements to the queue using add
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of the queue = " + priorityQueue.peek());
        //removing element by element from the queue using poll and print it out
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
        //put 5 new elements into the empty queue using offer
        for (int i = 10; i > 5; i--) {
            priorityQueue.offer(i);
        }
        System.out.println("now the head of the queue = " + priorityQueue.peek());
        System.out.println("the queue before removing 9:");
        System.out.println(priorityQueue);
        priorityQueue.remove(9);
        System.out.println("the queue after removing 9:");
        System.out.println(priorityQueue);
        //removing all the elements from the queue
        priorityQueue.clear();
        System.out.println(priorityQueue);
        //trying to print out the head of the empty Queue using peek - we'll get null
        System.out.println(priorityQueue.peek());
        //trying to print out the head of the empty Queue using element - we'll get the exception
        System.out.println(priorityQueue.element());
    }
}

Đầu ra:

the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
  at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
  at Priority2.main(Priority2.java:32)

Như bạn có thể thấy, cố gắng in phần đầu của Hàng đợi trống bằng phương thức element() dẫn đến NoSuchElementException .

Bộ so sánh PriorityQueue

• Bộ so sánh comparator() trả về bộ so sánh được sử dụng để sắp xếp thứ tự các phần tử trong hàng đợi. Trả về null nếu hàng đợi được sắp xếp theo thứ tự tự nhiên của các phần tử.

Hàng đợi ưu tiên Java, ví dụ với bộ so sánh

Chúng tôi đã sử dụng thứ tự tự nhiên (tăng dần) trong các ví dụ mã ở trên, nhưng đôi khi chúng tôi nên thay đổi nó. Đây là ví dụ về hàng đợi ưu tiên Java, nơi chúng tôi tạo lớp bộ so sánh nội bộ của riêng mình để triển khai giao diện Bộ so sánh. Bộ so sánh của chúng tôi sẽ sắp xếp các phần tử từ lớn nhất đến nhỏ nhất.

import java.util.PriorityQueue;
import java.util.Comparator;
 
class Priority3 {
    public static void main(String[] args) {
        // Creating a priority queue with myComparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of Queue = " + priorityQueue.peek());
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}
 
class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value = number1.compareTo(number2);
        //sorting elements from maximal to minimal
        if (value > 0) {
            return -1;
        } else if (value < 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

Đầu ra:

the head of Queue = 5
5
4
3
2
1

Phần đầu của Hàng đợi bây giờ không phải là phần tử tối thiểu mà là phần tử tối đa và thứ tự đã được thay đổi thành đảo ngược.

Lặp lại PriorityQueue bằng iterator

ProrityQueue là một phần của khung Bộ sưu tập và triển khai giao diện Iterable<> . Để lặp qua các phần tử của hàng đợi ưu tiên, bạn có thể sử dụng phương thức iterator() . Đây là một ví dụ:

import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;
 
class Priority4 {
   public static void main(String[] args) {
       // Creating a priority queue
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       //put 5 elements to the queue using add
       for (int i = 5; i > 0; i--) {
           priorityQueue.add(i);
       }
       //Iterating via iterator() method
       Iterator<Integer> iterator = priorityQueue.iterator();
       while (iterate.hasNext()) {
           System.out.print(iterator.next() + " ");
       }
   }
}

Đầu ra:

1 2 4 5 3 

Các phương thức PriorityQueue khác

• boolean contains(Object o) trả về true nếu hàng đợi chứa phần tử o.
• int size() trả về số phần tử trong hàng đợi này.
• Object[] toArray() trả về một mảng chứa tất cả các phần tử trong hàng đợi này.

Đây là một ví dụ:

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority5 {
   public static void main(String[] args) {
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       for (int i = 5; i > 0; i--) {
           priorityQueue.offer(i);
       }
 
       System.out.println("our queue: " + priorityQueue);
 
       System.out.println("Does our queue contain 8?  " + priorityQueue.contains(8));
       System.out.println("Does queue contain 5?  " + priorityQueue.contains(5));
 
       System.out.println("The quantity of queue elements: " + priorityQueue.size());
       Object[] myArray = priorityQueue.toArray();
       System.out.println("print out our array:");
       for (Object name : myArray) {
           System.out.println(name);
       }
   }
}

Đầu ra:

our queue: [1, 2, 4, 5, 3]
Does our queue contain 8?  false
Does our queue contain 5?  true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3

Định nghĩa PriorityQueue Java 8

Nếu bạn mở tài liệu về priorityqueue java 8, bạn sẽ tìm thấy ở đó định nghĩa tiếp theo: Một hàng đợi ưu tiên không giới hạn dựa trên một đống ưu tiên. Các phần tử của hàng đợi ưu tiên được sắp xếp theo thứ tự tự nhiên của chúng hoặc theo Bộ so sánh được cung cấp tại thời điểm xây dựng hàng đợi, tùy thuộc vào hàm tạo nào được sử dụng. Hàng đợi ưu tiên không cho phép các phần tử null. Hàng đợi ưu tiên dựa trên thứ tự tự nhiên cũng không cho phép chèn các đối tượng không thể so sánh được (làm như vậy có thể dẫn đến ClassCastException). Heap là một từ rất quan trọng ở đây. Nó giải thích các thuộc tính của thứ tự các phần tử Hàng đợi Ưu tiên.

Nguyên tắc hoạt động của PriorityQueue: Binary Heap

Hãy bắt đầu với một ví dụ. Hãy tạo hai đối tượng triển khai giao diện Hàng đợi. Một trong số họ LinkedList, thứ hai - PriorityQueue. Cả hai đều có 5 phần tử của Số nguyên (1,2,3,4 và 5) và chúng tôi bắt đầu đưa các phần tử vào hàng đợi của mình từ lớn nhất đến nhỏ nhất. Vì vậy, số đầu tiên là 5, sau đó là 4, 3, 2 và số cuối cùng sẽ là 1. Sau đó in ra cả hai danh sách để kiểm tra thứ tự.

   Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
       System.out.println("PriorityQueue: " + priorityQueue)

Kết quả của những mã này hoạt động là tiếp theo:

LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]

Chà, thứ tự danh sách liên kết có thể dự đoán được và dễ hiểu. Nó được sắp xếp theo nguyên tắc FIFO. Chúng tôi bắt đầu với 5, vì vậy phần tử này là phần tử đầu tiên trong dòng, sau đó là 4, v.v. Chúng ta có thể nói gì về thứ tự hàng đợi ưu tiên? Docs cho biết các phần tử của hàng đợi ưu tiên được sắp xếp theo thứ tự tự nhiên của chúng hoặc theo Bộ so sánh được cung cấp tại thời điểm xây dựng hàng đợi. Tuy nhiên, thứ tự này dường như không “tự nhiên” theo nghĩa sắp xếp tuyến tính. Chúng tôi muốn mong đợi [1, 2, 3, 4, 5], không phải [1, 2, 4, 5, 3]. Để hiểu tại sao thứ tự truy xuất lại như vậy, chúng ta nên nhớ lại hàng đợi ưu tiên đó dựa trên một đống. đống là gì? Nó là một cấu trúc dữ liệu dựa trên cây nhị phân. Thuộc tính chính của heap: mức độ ưu tiên của mỗi bậc cha mẹ lớn hơn mức độ ưu tiên của các phần tử con của nó. Hãy để tôi nhắc bạn rằng một cây được gọi là nhị phân đầy đủ nếu mỗi cha mẹ có không quá hai con và việc lấp đầy các cấp độ đi từ trên xuống dưới (từ cùng một cấp độ - từ trái sang phải). Heap nhị phân tự tổ chức lại mỗi khi các phần tử được thêm vào hoặc xóa khỏi nó. Trong trường hợp min-heap, phần tử nhỏ nhất sẽ chuyển đến thư mục gốc bất kể thứ tự chèn của nó. Hàng đợi ưu tiên dựa trên đống nhỏ này. Điều đó có nghĩa là, trong trường hợp các phần tử hàng đợi là số, phần tử đầu tiên của hàng đợi sẽ là phần tử nhỏ nhất trong số các số này. Nếu bạn xóa gốc, phần nhỏ nhất tiếp theo sẽ trở thành gốc.

Hãy chuyển sang ví dụ của chúng tôi.

Bước 1. Chúng tôi đặt '5' vào hàng đợi ưu tiên. Nó trở thành một gốc rễ. Bước 2. Chúng tôi thêm '4' vào hàng đợi ưu tiên. 4 <5, vì vậy phần tử mới phải cao hơn phần tử cũ. Số 4 trở thành gốc, số 5 là con trái của nó. Bây giờ cấu trúc dữ liệu trong Java là [4, 5] Bước 3. Chúng tôi thêm '3'. Tạm thời nó trở thành con phải của một gốc (4). Tuy nhiên, 3 < 4, vì vậy chúng ta nên nâng nó lên. Trao đổi 3 và 4. Bây giờ chúng ta có một cấu trúc chẳng hạn như [3, 5, 4] Bước 4. Chúng ta thêm '2'. Nó trở thành con trái của 5. 2<5, vì vậy hãy trao đổi chúng. 2 trở thành con trái của 3, 2 < 3, do đó thêm một quá trình trao đổi. Bây giờ chúng ta có một cấu trúc [2,3,4,5] Bước 5.Chúng tôi thêm '1'. Nó xuất phát từ con phải của 3 đến con trái của 2, rồi đi đến thư mục gốc. Cấu trúc dữ liệu kết quả: [1,2,4,5,3] Quá trình loại bỏ bắt đầu từ gốc và nó kích hoạt quy trình ngược lại. Vì vậy, đầu tiên chúng ta có 1 làm gốc, sau đó là 2, 3, 4 và cuối cùng là 5. Đó là lý do tại sao sử dụng thao tác loại bỏ poll()

while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }

chúng tôi đã "sắp xếp" ở đầu ra theo nghĩa tuyến tính:

1
2
3
4
5

Vì vậy, hàng đợi ưu tiên có thể có hiệu quả đối với một số hoạt động. Phải mất thời gian O(log N) để chèn và xóa từng phần tử và bạn có thể lấy phần tử tối thiểu trong O(1). Đây là ví dụ đầy đủ:

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

Điều quan trọng là phải hiểu rằng hàng đợi ưu tiên dựa trên đống nhị phân, vì vậy chúng không giữ các phần tử theo thứ tự được sắp xếp tuyến tính. Mọi cách từ gốc đến lá đều được sắp xếp, nhưng các cách khác nhau từ gốc thì không. Điều đó có nghĩa là bạn có thể lấy phần tử tối thiểu của hàng đợi rất nhanh.

Những điều bạn nên biết về hàng đợi ưu tiên. danh sách tóm tắt

• Hàng đợi ưu tiên không cho phép các đối tượng NULL.
• Bạn chỉ có thể thêm các đối tượng có thể so sánh được vào PriorityQueue.
• Hàng đợi ưu tiên được xây dựng dưới dạng một đống nhỏ, một loại cây nhị phân. Phần tử tối thiểu là một gốc. Các đối tượng của hàng đợi ưu tiên được sắp xếp mặc định theo thứ tự tự nhiên.
• Bạn có thể sử dụng Bộ so sánh nếu bạn cần đặt hàng tùy chỉnh.
• PriorityQueue không phải là chuỗi an toàn, vì vậy bạn nên sử dụng PriorityBlockingQueue để làm việc trong môi trường đồng thời.
• PriorityQueue cung cấp thời gian O(log(n)) cho các phương thức thêm và thăm dò ý kiến ​​và O(1) để nhận các phần tử tối thiểu.