PriorityQueue trong java với ví dụ cụ thể

Mục lục

1 Constructor PriorityQueue:
2 Method PriorityQueue

Queue được biết đến như là một cấu trúc dữ liệu sắp xếp các phần tử theo thuật toán First in First out. Tuy nhiên đối với PriorityQueue các phần tử mặc định sẽ được sắp xếp thứ tự theo tự nhiên ví dụ như đối với số nguyên sắp tăng dần theo giá trị, String thì tăng dần a – z etc. Chúng ta có thể thay đổi cách sắp xếp các phần tử bằng cách truyền vào Comparator và PriorityQueue sẽ sử dụng Comparator này để sắp xếp cách phần tử.

Một số điểm quan trọng trong PriorityQueue:

PriorityQueue không cho phép thêm giá trị null.
Nếu không cung cấp Comparator tại constructor thì PriorityQueue sẽ sử dụng Comparator mặc định.

Constructor PriorityQueue:

PriorityQueue(): Khởi tạo PriorityQueue mặc định và các phần tử được sắp xếp tự nhiên.
PriorityQueue(Collection<E> c): Khởi tạo Priority với các phần tử tử được clone từ Collection c.
PriorityQueue(int initialCapacity): Khởi tạo PriorityQueue với sức chứa initialCapacity.
PriorityQueue(int initialCapacity, Comparator<E> comparator): Khởi tạo PriorityQueue với sức chứa initialCapacity và comparator thay thế sắp xếp tự nhiên.
PriorityQueue(PriorityQueue<E> c): Khởi tạo PriorityQueue với các phần tử ban đầu được clone từ một PriorityQueue khác.
PriorityQueue(SortedSet<E> c): Khởi tạo PriorityQueue với các phần tử ban đầu được clone từ SortedSet khác.

Ví dụ 1

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.PriorityQueue;

public class Main {

    public static void main(String[] args) {

        PriorityQueue<String> pQueue = new PriorityQueue<>();

        // Adding items to the pQueue using add()
        pQueue.add("A");
        pQueue.add("G");
        pQueue.add("D");
        pQueue.add("J");

        System.out.println("Phan tu dau tien:" + pQueue.peek());


        System.out.println("Queue: ");
        Iterator itr = pQueue.iterator();
        while (itr.hasNext())
            System.out.println(itr.next());

        pQueue.poll();
        System.out.println("Sau khi xoa phan tu dau tien");
        Iterator<String> itr2 = pQueue.iterator();
        while (itr2.hasNext())
            System.out.println(itr2.next());

        pQueue.remove("G");
        System.out.println("Sau khi xoa phan tu G");
        Iterator<String> itr3 = pQueue.iterator();
        while (itr3.hasNext())
            System.out.println(itr3.next());

    }

}

Ví dụ 2: Giả sử mình có một PriorityQueue String, thông thường thì PriorityQueue sẽ tự động sắp xếp tăng dần từ a – z, A-Z. Bây giờ mình muốn nó sắp xếp giảm dần thì sẽ làm như sau

import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {

    public static void main(String[] args) {

        PriorityQueue<String> pQueue = new PriorityQueue<>(Comparator.comparing(String::toString).reversed());

        // Adding items to the pQueue using add()
        pQueue.add("A");
        pQueue.add("G");
        pQueue.add("D");
        pQueue.add("J");

        System.out.println(pQueue);
    }

}

Output: [J, G, D, A]

Output:

Phan tu dau tien:A
Queue:
A
G
D
J
Sau khi xoa phan tu dau tien
D
G
J
Sau khi xoa phan tu G
D
J

Method PriorityQueue

boolean add(E element): Thêm phần tử vào PriorityQueue.
public remove(Object o): Xoá phần tử o trong PriorityQueue.
public remove(): Xóa phần tử đầu tiên của PriorityQueue.
public poll(): Tương tự remove(), điểm khác nhau giữa poll() và remove(), poll() trả về null khi Queue rỗng còn remove() quăng exception NoSuchElementException.
public peek(): Trả về phần tử đầu tiên của Queue. Trả về null nếu PriorityQueue rỗng.
Iterator iterator(): Duyệt PriorityQueue.
boolean contains(Object o): Kiểm tra sự tồn tại của Object o trong PriorityQueue.
void clear(): Xóa toàn bộ các phần tử trong PriorotyQueue.
boolean offer(E e):Thêm phần tử vào PriorityQueue.
int size(): Trả về số lượng phần tử của PriorityQueue.
toArray(): Convert PriorityQueue sang Array.
Comparator comparator(): Lấy Comparator đang được sử dụng trong PriorityQueue

Bài tập:

Implementing Dijkstra’s and Prim’s algorithms.
Maximize array sum after K negations