Priority Queue! Let's break it down and learn about this part of Data Structure.

Queue

Queue, like the Stack, is a specialization of the List. It is based on the FIFO basis - first in, first out, which means that the first in is the first out. In other words, the “oldest” person in the queue leaves first, for better understanding, consider a bank queue.

⚠️

Queue Applications: Process management in operating systems; Communication between tasks in concurrent programming; computer networks (printing); response to requests on a Web server

Queues themselves only allow direct manipulation of data at the ends.

public interface Queue<E> {
    void enqueue(E value); //enfileira
    E dequeue(); //remove e desenfileira
    E first(); //retorna primeiro elemento
    int size(); //algumas literaturas se chama lenght()
    boolean isEmpty();
}

Priority Queue

It resembles the behavior of a common everyday queue, but now consider that you are in line at a bank and a lady enters the queue, everyone lets her go ahead as she has greater PRIORITY as she is more old.

In the Priority Queue Data Structure, each node has a Key-Value, Key is the key that stores its priority, Value is the value of the node. By Java default, the Key is initially numeric and can be changed by the programmer later.

The set of a Key and Value is called Entry, so the interface of this E.D changes. Other details are: after the Key is defined, it cannot be changed. If two nodes have the same priority value in the Key, the programmer chooses the rule.

public interface PriorityQueueOg<K,V> {
    void insert(K key, V value);
    Entry<K,V> remove();
    int size();
    boolean isEmpty();
}

In the next structures, we will use the classes for Node and Entry, first, last and size attributes, and compareTo

The priority queue is divided into two: the sorted (Sorted Priority Queue) and the unsorted (Unorted Priority Queue)

Sorted Priority Queue

Ordered list takes care of inserting the node in the right position, so removal is easy, just remove the first one (if the programmer doing the E.D defines that the highest priority element should be at the beginning)

To know which node has the highest priority we use compareTo, a Collections function that, through its return, we can obtain crucial results for the execution of this E.D, if the return is:

• Negative: If the object that calls the method is "smaller" than the object passed as a parameter.
• Zero: If the objects are equal.
• Positive: If the object that calls the method is "larger" than the object passed as a parameter.

Insert

To enter you must check a few things

1st step → Create a new node

Node newNode = new Node(key, value)

2nd step → Check if the Queue is empty, if so, place the Head and Last as the new node, considering that it will be the only one

public interface Queue<E> {
    void enqueue(E value); //enfileira
    E dequeue(); //remove e desenfileira
    E first(); //retorna primeiro elemento
    int size(); //algumas literaturas se chama lenght()
    boolean isEmpty();
}

3rd step → If it is not the only element in the list, you must check whether the new node, compared to the first, has higher priority or not.

public interface PriorityQueueOg<K,V> {
    void insert(K key, V value);
    Entry<K,V> remove();
    int size();
    boolean isEmpty();
}

3rd step → Then compare with the last element in the list

Node newNode = new Node(key, value)

4th step → If not everything else, only the middle is left! To do this, we need to make an auxiliary node to go in front of the newNode (nN) and compare the two, the comparison ends when the auxNode points to nothing, or when the nN is greater than the auxNode (larger, so it is behind in line). This while is used for the aux to go around and compare the value of the two nodes, when it finds it, it places the nN behind the auxNode

        if(isEmpty()){
            first = newNode;
            last = newNode;
        }else{

Remove

The remove method in Sorted is much simpler because, as already mentioned, the Queue is already organized for it.

1st step → As every Remove method returns the element it will remove, the step will be to create an Entry (Why not a node?)

         if(compare(newNode, first)<0){
                 //Se o nN for menor que o F
                 //Levando em consideração que a prioridade maior é 0
                 //Se o nN for menor que F, ele será o de maior prioridade pegando o lugar do primeiro
                newNode.next = first;
                first.previous = newNode;
                first = newNode;
          }

2nd step → Then, as you are already going to eliminate the first node, just point First to the one next to First

             }else if(compare(newNode, last)>=0){
           //Se o nN for maior que o L
           //Significa que o número de nN é maior que L
           //Então bota o nN para ultimo
                newNode.previous=last;
                last.next=newNode;
                last = newNode;
            }else{

3rd step → Check if there is only one element in the Queue, because if so, the Queue will be empty! Then you will have to set F and L to null

            }else{
                //se nao for nada, está no meio
                //entao temos que achar entre qual dos meios
                Node auxNode = first;
                while(compare(newNode, auxNode)>0 && auxNode.next!=null){
                    //enquanto o newNode tiver prioridade maior que o auxiliar
                    //e o auxiliar tiver um proximo
                    auxNode = auxNode.next;
                }
                newNode.next = auxNode;
                newNode.previous = auxNode.previous;
            }
        }

4th step → If it’s not the only element, it means there are others! So, when you remove the first one in step 2, what was previously First is still there being connected by the previous one, so we must:

        Entry<K,V> max = maxPriority();

MaxPriority

Method that returns the highest priority element in the list, and since we are in order, it only returns the first one.

        first = first.next;

Asymptotic Analysis

Método	O(_)
size	O(1)
isEmpty	O(1)
insert	O(n)
remove	O(1)
maxPriority	O(1)

Unsorted Priority Queue

The disordered Queue is very different from the ordered one! Let's start with his methods:

Insert

To add to unsorted, like and disordered, you don't need to worry about where this new element will be, just add it at the end!

1st step → Check if the list is empty, because if it is, the node to be added will be the first (First) and the last (Last)

public interface Queue<E> {
    void enqueue(E value); //enfileira
    E dequeue(); //remove e desenfileira
    E first(); //retorna primeiro elemento
    int size(); //algumas literaturas se chama lenght()
    boolean isEmpty();
}

2nd step → if it is not empty, just worry about adding this node at the end!

public interface PriorityQueueOg<K,V> {
    void insert(K key, V value);
    Entry<K,V> remove();
    int size();
    boolean isEmpty();
}

MaxPriority

Remove in Unsorted is much more complex than the measly lines of code in Sorted…

“Why?” you ask, we should use a method (which in the other version was much simpler too) called maxPriority, whose objective is to find the node with the highest priority. Previously it was taught in a simple way with just a few lines of code, now, because we don't know where this highest priority node actually is, we must go through the entire queue in search of it! So before we look at remove itself, we'll look at maxPriority.

1st step → Whenever we want to traverse a data structure, we need two nodes: an auxiliary one to always go ahead, and the one we want to achieve (which in this case is MaxPriority)

Node newNode = new Node(key, value)

2nd step → These two will run within a node, it only ends when the aux reaches null (end of the queue). Compare these nodes and if it is negative, it means that the aux is smaller than the max, so the max is the largest, updating the value of the max Node, and then making the aux run.

        if(isEmpty()){
            first = newNode;
            last = newNode;
        }else{

Remove

1st step → In all emoves, create a variable that will store the node that will be removed. In this case, you already know which one will be removed because you are calling the maxPriority
method

         if(compare(newNode, first)<0){
                 //Se o nN for menor que o F
                 //Levando em consideração que a prioridade maior é 0
                 //Se o nN for menor que F, ele será o de maior prioridade pegando o lugar do primeiro
                newNode.next = first;
                first.previous = newNode;
                first = newNode;
          }

2nd step → Then check if it is the only element, if so, F and L are nulls!

             }else if(compare(newNode, last)>=0){
           //Se o nN for maior que o L
           //Significa que o número de nN é maior que L
           //Então bota o nN para ultimo
                newNode.previous=last;
                last.next=newNode;
                last = newNode;
            }else{

3rd step → If it is not the only one, there are other options: if the max is the last one, eliminate last, if it is the first, eliminate the first, if it is neither two two, it is in the middle!

            }else{
                //se nao for nada, está no meio
                //entao temos que achar entre qual dos meios
                Node auxNode = first;
                while(compare(newNode, auxNode)>0 && auxNode.next!=null){
                    //enquanto o newNode tiver prioridade maior que o auxiliar
                    //e o auxiliar tiver um proximo
                    auxNode = auxNode.next;
                }
                newNode.next = auxNode;
                newNode.previous = auxNode.previous;
            }
        }

4th step → If it is in the middle, the max that is in the crowd will have to be removed, this occurs when no one else points to it.

        Entry<K,V> max = maxPriority();

Asymptotic Analysis

Método	O(_)
size	O(1)
isEmpty	O(1)
insert	O(1)
remove	O(n)
maxPriority	O(n)

The above is the detailed content of Priority Queue! Let's break it down and learn about this part of Data Structure.. For more information, please follow other related articles on the PHP Chinese website!