Sorting using a priority queue

Since a priority queue always returns the minimum element, if we insert all input elements and then keep dequeuing them, they would be dequeued in sorted order. This can be used to sort a list of elements. In our example, we will add a new method called the LinkedList implementation. This implementation sorts the elements using PriorityQueue. First insert all the elements into the priority queue. Then, dequeue the elements and append them back to the linked list:

public void sort(Comparator<E> comparator){
    PriorityQueue<E> priorityQueue = new LinkedHeap<E>(comparator);

    while (first!=null){
        priorityQueue.enqueue(getFirst());
        removeFirst();
    }

    while (priorityQueue.checkMinimum()!=null){
        appendLast(priorityQueue.dequeueMinimum());
    }
}

Both enqueue and dequeue have θ(lg n) complexity, and we have to enqueue and dequeue each of the elements. We have already seen this: lg 1 + lg 2 + … + lg n = θ(n lg n...