1. Structure de données PriorityQueue
La structure des données de PriorityQueue (file d'attente de priorité) dans JDK7 est un tas binaire. Pour être précis, c'est une plus petite pile.
Un tas binaire est un tas spécial, qui est approximativement un arbre binaire complet. Le tas binaire satisfait les caractéristiques: la valeur clé du nœud parent maintient toujours une relation d'ordre fixe avec la valeur clé de tout nœud enfant, et le sous-arbre gauche et le sous-arbre droit de chaque nœud sont un tas binaire.
Le tas maximum est lorsque la valeur clé du nœud parent est toujours supérieure ou égale à la valeur clé de tout nœud enfant. Le tas minimum est lorsque la valeur clé du nœud parent est toujours inférieure ou égale à la valeur de clé de tout nœud enfant.
La figure suivante est un tas maximum
L'en-tête de l'équipe PriorityQueue est le plus petit élément de l'ordre donné.
PriorityQueue ne permet pas les valeurs nuls et ne prend pas en charge les objets non combinables. PriorityQueue nécessite l'utilisation d'interfaces comparables et de comparaison pour trier les objets, et les éléments en eux seront traités en fonction de la priorité lors du tri.
La taille de PriorityQueue est illimité, mais la taille initiale peut être spécifiée lors de la création. Lors de l'ajout d'éléments de file d'attente, la file d'attente se développera automatiquement.
PriorityQueue n'est pas une file d'attente, la priorité de BlockingQueue similaire est une file d'attente.
Nous savons que les files d'attente suivent le premier mode de sortie, mais parfois les objets doivent être traités en fonction de la priorité dans la file d'attente. Par exemple, nous avons une application qui génère des rapports d'actions pendant les heures de négociation quotidiennes, ce qui nécessite de traiter beaucoup de données et prend beaucoup de temps de traitement. Lorsque le client envoie une demande à cette application, elle entre en fait dans la file d'attente. Nous devons d'abord faire face aux clients prioritaires, puis aux utilisateurs ordinaires. Dans ce cas, la priorité de Java (file d'attente de priorité) sera très utile.
PriorityQueue est une file d'attente illimitée basée sur le tas de priorité. Les éléments de cette file d'attente de priorité peuvent être triés naturellement par défaut ou triés lorsque la file d'attente est instanciée par le comparateur fourni.
Les files d'attente prioritaires ne permettent pas les valeurs nuls et ne prennent pas en charge les objets non combinables, tels que les classes définies par l'utilisateur. La file d'attente prioritaire nécessite l'utilisation d'interfaces Java comparables et de comparaison pour trier les objets, et les éléments en eux seront traités en fonction de la priorité lors du tri.
L'en-tête de la file d'attente prioritaire est le plus petit élément basé sur le tri naturel ou le tri du comparateur. Si plusieurs objets ont le même type, il est possible de prendre au hasard l'un d'eux. Lorsque nous obtenons la file d'attente, nous retournons l'objet d'en-tête de la file d'attente.
La taille de la file d'attente prioritaire est sans restriction, mais la taille initiale peut être spécifiée au moment de la création. Lorsque nous ajoutons des éléments à la file d'attente prioritaire, la taille de la file d'attente augmentera automatiquement.
PriorityQueue est non-thread-sate, donc Java fournit PriorityBlockingQueue (implémentation de l'interface BlockingQueue) pour les environnements multithreads Java.
2. Analyse du code source de PriorityQueue
membre:
Privte Transient Object [] Direction; private int size = 0;
1. Le processus de construction d'un petit tas supérieur par prioritaire
Ici, nous utilisons le constructeur PriorityQueue pour passer dans un conteneur comme le paramètre PriorityQueue (ColleCntion <? Étend E> Exemple:
Le processus de construction d'un petit tas supérieur est à peu près divisé en deux étapes:
Copiez les données des conteneurs et vérifiez si les données des conteneurs sont nuls
INIMELLES DE VOID PRIVATEFROMCOLLECTION (Collection <? Étend E> C) {objet [] a = c.toArray (); // Si C.ToArray ne renvoie pas l'objet [], copiez-le. if (a.getClass ()! = objet []. Classe) a = arrays.copyof (a, a.length, objet []. class); int len = a.Length; if (len == 1 || this.comparator! = null) for (int i = 0; i <len; i ++) if (a [i] == null) lancez new nullpointerException (); this.queue = a; this.size = a.length;} Ajustez pour faire en sorte que les données satisfont la structure du petit tas supérieur.
Tout d'abord, deux méthodes d'ajustement: Siftup et Siftdown
Siftdown: Lorsqu'un élément d'initialisation est donné, l'élément doit être ajusté de sorte qu'il répond aux propriétés structurelles du tas minimum. Par conséquent, la valeur clé de l'élément X est constamment comparée et échangée avec l'enfant de haut en bas jusqu'à ce qu'il soit constaté que la valeur clé de l'élément X est inférieure ou égale à la valeur clé de l'enfant (c'est-à-dire qu'elle est garantie d'être plus petite que ses valeurs de nœud gauche et droite), ou il tombe au nœud foliaire.
Par exemple, comme indiqué dans le diagramme suivant, ajustez ce nœud 9:
private void siftdowncomparable (int k, e x) {comparable <? super e> key = (comparable <? super e>) x; int half = size >>> 1; // taille / 2 est l'indice du premier nœud de feuille // tant que le nœud feuille n'est pas atteint tandis que (k <moitié) {int child = (k << 1) + 1; // l'objet enfant gauche c = file d'attente [enfant]; int droit = enfant + 1; // découvrez les enfants les plus petits et les plus petits des enfants gauche et droit (droite <size && ((comparable <? Super E>) C) .Compareto ((e) file d'attente [à droite])> 0) C = file d'attente [enfant = droit]; if (key.compareto ((e) c) <= 0) pause; file d'attente [k] = c; k = enfant; } file d'attente [k] = key;} Siftup: PriorityQueue insère le nouvel élément dans la queue chaque fois qu'un nouvel élément est ajouté. Par conséquent, il devrait y avoir le même processus d'ajustement que Siftdown, sauf pour s'ajuster du bas (feuille) vers le haut.
Par exemple, remplissez le nœud avec la clé 3 dans le diagramme suivant:
private void siftupPomparable (int k, e x) {comparable <? super e> key = (comparable <? super e>) x; while (k> 0) {int parent = (k - 1) >>> 1; // obtient l'objet d'indice parent e = file d'attente [parent]; if (key.compareto ((e) e)> = 0) pause; file d'attente [k] = e; k = parent; } file d'attente [k] = key;}Le processus global de construction d'un petit tas supérieur est:
private void initFromCollection (Collection <? étend E> c) {INIMELlementsFromCollection (C); lourd(); }Parmi eux, Heapify est le processus de Siftdown.
2. Processus d'extension de la capacité Priorityqueue
Comme le montre les membres de l'instance, PriorityQueue maintient un objet [], donc sa méthode d'extension est similaire à la table de commande ArrayList.
Seul le code source de la méthode de croissance est donné ici
private void Grow (int mincapacity) {int oldcapacity = queue.length; // double taille si petit; sinon croître de 50% int newcapacity = oldcapacity + ((oldcapacity <64)? (oldcapacity + 2): (oldcapacity >> 1)); // Code consciente du trop-plein if (newCapacity - max_array_size> 0) newCapacity = HugeCapacity (mincapacity); queue = arrays.copyof (file d'attente, newCapacity); }On peut voir que lorsque la capacité du tableau n'est pas grande, la capacité n'est pas grande à chaque fois. Lorsque la capacité du tableau est supérieure à 64, le double est élargi à chaque fois.
3. Application PriorityQueue
EG1:
Voici l'application la plus simple: trouvez le plus grand numéro K -th à partir de données dynamiques.
L'idée est de maintenir une petite pile supérieure avec une taille = k.
// Données sont des données dynamiques // TEAP maintient les données dynamiques // Res est utilisée pour enregistrer la valeur K-Most Public Boolean Kthlar plus importante (ints int, int k, priorityqueue <nteger> tas, int [] res) {if (heap.size () <k) {heap.offrer (data); if (heap.size () == k) {res [0] = heap.Peek (); Retour Vrai; } return false; } if (Heap.Peek () <data) {Heap.Poll (); tas.offer (données); } res [0] = Heap.Peek (); Retour Vrai; }
EG2:
Nous avons un client de classe utilisateur qui ne fournit aucune sorte. Lorsque nous l'utilisons pour créer une file d'attente prioritaire, nous devons lui fournir un objet comparateur.
Client.java
package com.journalv.collections; Client de classe publique {private int id; nom de chaîne privé; Customer public (int i, string n) {this.id = i; this.name = n; } public int getID () {return id; } public String getName () {Nom de retour; }} Nous utilisons des nombres aléatoires Java pour générer des objets utilisateur aléatoires. Pour le tri naturel, nous utilisons un objet entier, qui est également un objet Java encapsulé.
Voici le code de test final montrant comment utiliser PriorityQueue:
PriorityqueUeExample.java
package com.journalv.collections; Importer java.util.comparator; import java.util.priorityqueue; import java.util.queue; import java.util.random; classe publique priorityqueUeExample {public static void main (String [] args) {// Priority Fitre Natural Tri Exemple Exemple <Integer> IntegerPriorityQueue = Nouveau priorityQueue <> (7); Random Rand = new Random (); pour (int i = 0; i <7; i ++) {IntegerPriorityQueue.add (new Integer (rand.nextint (100))); } pour (int i = 0; i <7; i ++) {Integer dans = IntegerPriorityQueue.poll (); System.out.println ("Traitement entier:" + in); } // Exemple d'utilisation de la file d'attente de priorité Exemple de file d'attente <Sisest CustomerPriorityQueue = new priorityQueue <> (7, idComparator); addDatatoqueue (CustomerPriorityQueue); Poldatafromqueue (CustomerPriorityQueue); } // Anonymous Comparator implémente le comparateur statique public <Simité> idComparator = new Comparator <Simité> () {@Override public int compare (Client C1, Client C2) {return (int) (c1.getID () - C2.Getid ()); }}; // Méthode universelle utilisée pour ajouter des données à la file d'attente Static Void addDatatoqueue (file d'attente <Sivet> CustomerPriorityQueue) {Random Randage = new Random (); pour (int i = 0; i <7; i ++) {int id = rand.nextint (100); CustomerPriorityQueue.add (nouveau client (id, "Pankaj" + ID)); }} // Méthode générale pour récupérer les données à partir d'une file d'attente Private Static Void PoldataFromQueue (file d'attente <Sitret> CustomerPriorityQueue) {while (true) {Customer Cust = CustomerPriorityQueue.poll (); if (cust == null) casser; System.out.println ("Traitement Client avec id =" + cust.getId ()); }}}} Notez que j'utilise Java Anonymous Class qui implémente l'interface du comparateur et implémente un comparateur basé sur ID.
Lorsque j'exécute le programme de test ci-dessus, j'obtiens la sortie suivante:
Traitement entier: 9 Processeur entier: 16 Processement entier: 18 Processement entier: 25 Processement entier: 33 Processement entier: 75 Processement entier: 77 Processement ID = 82 Procédé client avec ID = 96
D'après les résultats de sortie, on peut voir clairement que le plus petit élément est ensuite éliminé d'abord à la tête de la file d'attente. Si le comparateur n'est pas mis en œuvre, une classCastException sera lancée lors de la création d'une CustomerPriorityQueue.
Exception in thread "main" java.lang.ClassCastException: com.journaldev.collections.Customer cannot be cast to java.lang.Comparable at java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:633) at java.util.PriorityQueue.siftUp(PriorityQueue.java:629) at java.util.priorityqueue.offer (priorityqueue.java:329) sur java.util.priorityqueue.add (priorityqueue.java:306) sur com.journaldev.collections.priorityqueexample.adddatatoqueue (priority-ueued com.journaldev.collections.priorityqueUeExample.main (priorityqueUeExample.java:25)