What is the difference between a PriorityQueue and a TreeSet in terms of usage and performance?

Both PriorityQueue and TreeSet are implementations of the SortedSet interface, which means they maintain their elements in a sorted order. However, there are some differences between these two implementations in terms of usage and performance.

Usage:

PriorityQueue: It is a queue data structure in which elements are processed based on their priority. The element with the highest priority is removed first. The priority can be either natural ordering (e.g., numbers, strings) or custom ordering (e.g., based on a specific property of an object).

TreeSet: It is a set data structure in which elements are stored in a sorted order. TreeSet uses the natural ordering of elements or a custom comparator to sort its elements.

Performance:

PriorityQueue: It is implemented as a binary heap, which offers O(log n) time for insertion and removal operations. This makes it efficient for maintaining a sorted list of elements in a queue. However, accessing elements in the middle of the queue is not efficient, and the performance can degrade to O(n) for certain operations.

TreeSet: It is implemented as a self-balancing binary search tree, which offers O(log n) time for insertion, removal, and searching operations. This makes it efficient for maintaining a sorted list of elements in a set. The performance for accessing elements in the middle of the set is also efficient.

Here is an example code snippet demonstrating the usage of PriorityQueue and TreeSet:

import java.util.*;

public class PriorityQueueVsTreeSetExample {
    public static void main(String[] args) {
        // PriorityQueue example
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        pq.add(10);
        pq.add(5);
        pq.add(15);
        System.out.println("PriorityQueue: " + pq); // [15, 5, 10]
        System.out.println("Polling the highest priority element: " + pq.poll()); // 15
        System.out.println("PriorityQueue after polling: " + pq); // [10, 5]

        // TreeSet example
        TreeSet<String> ts = new TreeSet<>();
        ts.add("apple");
        ts.add("banana");
        ts.add("orange");
        System.out.println("TreeSet: " + ts); // [apple, banana, orange]
        System.out.println("First element: " + ts.first()); // apple
        System.out.println("Last element: " + ts.last()); // orange
        System.out.println("Removing banana: " + ts.remove("banana")); // true
        System.out.println("TreeSet after removing banana: " + ts); // [apple, orange]
    }
}

In this example, we created a PriorityQueue of integers in reverse order, which means the highest priority element will be polled first. We added some elements to the PriorityQueue and demonstrated how to poll the highest priority element.

Next, we created a TreeSet of strings and added some elements to it. We demonstrated how to retrieve the first and last elements of the set and how to remove an element from it.