File d'attente prioritaire PriorityQueue du framework de collection Java

Cet article vous apporte des connaissances pertinentes sur java, qui présente principalement les connaissances pertinentes sur la file d'attente prioritaire PriorityQueue. Le framework de collection Java fournit deux types de files d'attente prioritaires, PriorityQueue et PriorityBlockingQueue est un thread. Ce n'est pas sûr. -safe. Jetons-y un coup d'oeil. J'espère que cela sera utile à tout le monde.

Apprentissage recommandé : "Tutoriel vidéo Java"

Le framework de collection Java fournit deux types de files d'attente prioritaires, PriorityQueue et PriorityBlockingQueue PriorityQueue n'est pas sécurisé pour les threads et PriorityBlockingQueue est sécurisé pour les threads. Cet article est principalement sécurisé. présente PriorityQueue

La relation de prioritéQueue dans le framework de collection Java est la suivante :

1. Notes sur l'utilisation de PriorityQueue

1. Lorsque vous l'utilisez, vous devez importer le package où se trouve PriorityQueue, c'est-à-dire :

import java.util.PriorityQueue

2. Les éléments placés dans PriorityQueue doivent être de taille comparable. Les objets dont la taille ne peut pas être comparée ne peuvent pas être insérés, sinon une
ClassCastException sera levée. 3. Un objet nul ne peut pas être inséré, sinon il sera généré NullPointerException

4 Il n'y a pas de limite de capacité, vous pouvez insérer n'importe quel nombre d'éléments et sa capacité interne peut être automatiquement étendue

5. L'utilisation sous-jacente de PriorityQueue La structure de données du tas

7 est un petit tas par défaut --- c'est-à-dire que les éléments obtenus à chaque fois sont les plus petits. éléments (Si nous voulons devenir un grand tas, nous devons re-comparer la méthode. La méthode de comparaison par défaut est la méthode compareTo dans l'interface Comparable)

2. Introduction aux interfaces communes de PriorityQueue

1. File d'attente prioritaire Voici quelques méthodes de construction courantes dans

PriorityQueue

, vous pouvez vous référer au document d'aide aux autres.

Constructor

Introduction à la fonctionLa capacité par défaut est 11Créer une initiale Une priorité file d'attente avec une capacité de initialCapacity, initialCapacity ne peut pas être inférieure à 1, sinon une IllegalArgumentException sera levée Utilisez une collection pour créer une file d'attente prioritaire PriorityQueue(Comparator<? super E> comparator)Crée une file d'attente prioritaire avec initialCapacity , comparez ses éléments selon le comparateur

PriorityQueue()	Créer une file d'attente prioritaire vide,
	PriorityQueue(int initialCapacity)
Remarque :	SouventPriorityQueue(Collection extends E> c)
capacité initiale par défaut et évalue ses éléments en fonction du comparateur spécifiéPriorityQueue(Comparator<? super E> comparator)	创建具有默认初始容量的优先级队列，并根据指定的比较器对其元素进行比较
PriorityQueue(int initialCapacity, Comparator <? super E> comparator)	创建一个初始容量为<strong>initialCapacity</strong>的优先级队列 Comparer PriorityQueue(int initialCapacity, Comparator <? super E> comparator) Créez une file d'attente prioritaire avec une capacité initiale de

spécifié par 🎜🎜🎜🎜Remarque : 🎜🎜initialCapacity ne peut pas être inférieur à 1, sinon une IllegalArgumentException sera levée 🎜généralement🎜🎜🎜🎜🎜

2. Comparaison des éléments dans PriorityQueue

Après avoir lu la méthode de construction, réfléchissons à nouveau à une question

Comment la file d'attente prioritaire parvient-elle à l'ordre ? Parce que la file d'attente prioritaire est implémentée à l'aide du petit tas racine

Dans le processus d'implémentation du petit tas racine, nous savons qu'une comparaison des éléments doit avoir lieu, donc les éléments de PriorityQueue doivent pouvoir comparer en taille , alors comment PriorityQueue effectue-t-il la comparaison des éléments ?

PriorityQueue adopte deux méthodes :
Comparble et Comparator.

1. Comparble est la méthode de comparaison interne par défaut Si l'utilisateur insère un objet de type personnalisé , l'objet doit implémenter l'interface Comparble et remplacer la méthode compareTo

2. objet, si l'utilisateur insère un objet de type personnalisé, il doit fournir une classe de comparaison, laisser la classe implémenter l'interface Comparator et remplacer la méthode de comparaison.

Nous voyons que le programme a signalé une erreur ici, pourquoi ? Parce que l'objet Enfant que nous avons inséré n'est pas comparable (

c'est-à-dire qu'il n'implémente pas l'interface Comparable et n'utilise pas de comparateur personnalisé)

Vous pouvez voir

Autrement dit, nous utilisons la méthode de comparaison par défaut dans la méthode compareTo de l'interface Comparable

À ce stade, nous examinons à nouveau le message d'erreur

Il semble qu'il y ait un problème lors de l'insertion d'éléments dans la PriorityQueue

Ensuite, ouvrons le code source de PriorityQueue et jetez un œil (

ci-dessous) C'est le code source de la méthode d'offre dans PriorityQueue)

Regardez à nouveau le code source de shiftUp

Continuez à cliquer sur siftUpComparable

En ce moment, revenons en arrière et jetons un œil à l'objet Child que nous avons mis dans PriorityQueue ,

Il n'a ni de comparateur personnalisé ni n'implémente l'interface Comparable,bien sûr, il signale une erreur !

D'accord, implémentons l'interface Comparable dans la classe Child et comparons par âge

import java.util.PriorityQueue;
class Child implements Comparable<Child>{
    int age;
    String name;

    public Child(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public int compareTo(Child o) {
        return this.age - o.age;  // 默认实现小根堆
    }

    @Override
    public String toString() {
        return "Child{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}
public class TestPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Child> priorityQueue = new PriorityQueue<>();

        priorityQueue.offer(new Child(12, "小亮"));
        priorityQueue.offer(new Child(11, "小红"));
        priorityQueue.offer(new Child(8, "小强"));
        System.out.println(priorityQueue);
    }
}

Si vous souhaitez implémenter un grand tas racine, c'est facile

Nous avons implémenté l'interface Compable ci-dessus , alors si Et si nous personnalisions un comparateur d'âge ?

class Child {
    int age;
    String name;

    public Child(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Child{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}
class AgeComparator implements Comparator<Child> {

    @Override
    public int compare(Child o1, Child o2) {
        return o1.age - o2.age; // 实现小根堆
        // return o2.ae - o1.age 实现大根堆
    }
}
public class TestPriorityQueue {
    public static void main(String[] args) {
        AgeComparator ageComparator = new AgeComparator();
        // 创建具有默认初始容量的 PriorityQueue ，并根据指定的比较器对其元素进行排序。
        PriorityQueue<Child> priorityQueue = new PriorityQueue<>(ageComparator);
        // 可以看到这里我的Child对象虽然没有实现Comparable接口，但因为我们对Child对象自定义了一个年龄比较器，所以插入元素不会报错
        priorityQueue.offer(new Child(12, "小亮"));
        priorityQueue.offer(new Child(11, "小红"));
        priorityQueue.offer(new Child(8, "小强"));
        System.out.println(priorityQueue);
    }
}

3. Insérer/supprimer/obtenir l'élément de priorité la plus élevée

Nom de la fonctionIntroduction à la fonctionbooleanInsérer l'élément e, insérer avec succès true. Si l'objet e est vide, une NullPointerException est levée. La complexité temporelle est E peek() pour obtenir l'élément avec le plus haut. priorité Si la file d'attente prioritaire est vide, renvoie nullE poll() supprime l'élément de priorité la plus élevée et le renvoie, si la file d'attente prioritaire est vide, renvoie nullint size()Get. le nombre d'éléments valides Clear Isemty () 》

offer(E e)	Remarque : lorsque l'espace n'est pas suffisant, il sera étendu
	Levoidar Clear ()
	Boolean
Détecte si la file d'attente prioritaire est vide, pour les retours vides à True

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!