Introduction aux scénarios d'application et aux méthodes d'implémentation du tas Java

1. Création d'un tas

1. Ajustez vers le bas (prenez un petit tas comme exemple)

Laissez le parent marquer le nœud qui doit être ajusté et l'enfant marque l'enfant gauche du parent (remarque : si le parent a un enfant, il doit d'abord avoir un enfant gauche)

Si l'enfant gauche du parent existe, c'est-à-dire : enfant

• Si l'enfant droit du parent existe , trouvez le plus petit enfant parmi les enfants de gauche et de droite, et laissez l'enfant le marquer

• Comparez le parent avec l'enfant plus petit, si :

le parent est plus petit que le plus petit enfant, l'ajustement se termine Sinon : échanger le parent avec le plus petit enfant, une fois l'échange terminé, le plus grand élément du parent. Un déplacement vers le bas peut empêcher le sous-arbre de satisfaire les propriétés du tas, il doit donc continuer à être ajusté vers le bas, c'est-à-dire parent = enfant ; enfant = parent*2+1, puis passez à l'étape 2.

public void shiftDown(int[] elem,int parent,int len){
        int cur=parent*2+1;
        while(cur<len){
           if(cur+1<len){
               if(elem[cur+1]<elem[cur]){
                   cur++;
               }
           }
            if(this.elem[cur]<this.elem[parent]) {
                swap(cur, parent);
            }
            parent=cur;
            cur=parent*2+1;
        }
    }

2. Créer un tas

Pour une séquence normale, nous devons commencer à ajuster à partir de son premier nœud parent avec un nœud gauche jusqu'à ce que l'arbre entier satisfasse les propriétés d'un tas.

3. Complexité temporelle de la création d'un tas

Le tas doit être un arbre binaire complet, et un arbre binaire complet est également un arbre binaire complet. D'après le calcul suivant, la complexité temporelle de la création d'un tas est O(n)

2. Insertion et suppression du tas

1. Insertion du tas

• Mettez l'élément à insérer à la fin du tas. tas, S'il ne peut pas être libéré, augmentez la capacité

• Ajustez le nœud nouvellement inséré vers le haut jusqu'à ce qu'il réponde aux propriétés du tas

【Ajustement vers le haut】

public void shiftUp(int elem[],int child){
        int parent=(child-1)/2;
        while(parent>=0){
            if(elem[child]>elem[parent]){
                swap(child,parent);
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }

2.

Selon les propriétés du tas, ce qui est supprimé doit être l'élément supérieur du tas. Les étapes sont les suivantes :

• Échangez l'élément supérieur du tas avec le dernier élément

• Diminuez le nombre d'éléments dans le tas d'un

• Ajustez l'élément supérieur du tas vers le bas

3. Application du tas

1. Tri du tas

Ordre croissant : créez un grand tas racine

Ordre décroissant : créez un petit tas racine

Échangez l'élément supérieur du tas et le dernier élément du tas , et ajustez vers le bas jusqu'à ce que le tas soit en ordre.

2. Problème Top-k [Trouver le plus petit nombre K]

Problème top-k : trouver les k premiers éléments grands ou petits dans l'ensemble de données.

class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] array=new int[k];
        if(arr==null||arr.length<=k||k==0){
            return array;
        }
        PriorityQueue<Integer> queue=new PriorityQueue<>((a,b)->b-a);
        int i=0;
        for(;i<k;++i){
            queue.offer(arr[i]);
        }
        while(i<arr.length){
            if(arr[i]<queue.peek()){
                queue.poll();
                queue.offer(arr[i]);
            }
            i++;
        }
        int size=queue.size();
        for(int j=0;j<size;++j){
            array[j]=queue.poll();
        }
        return array;
    }
}

IV. Introduction aux interfaces communes

1 Caractéristiques de PriorityQueue

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 présente principalement PriorityQueue.

[PriorityQueue] Notes d'utilisation :

• doit importer le package de PeioriryQueue ;

• Les éléments placés doivent être de taille comparable, sinon une ClassCastException sera levée ;

• ne peut pas placer d'éléments nuls ; , NullPointerException sera levée ;

• Vous pouvez insérer autant d'éléments que vous le souhaitez et la capacité interne sera automatiquement étendue

• La couche inférieure utilise une structure de données en tas, et la valeur par défaut est un petit tas ; Si vous souhaitez créer un gros tas, vous devez fournir un comparateur.

Méthode d'extension PriorityQueue :

• Si la capacité est inférieure à 64, elle est augmentée de 2 fois par rapport à oldCapacity

• Si la capacité est supérieure ou égale à 64, elle est étendue de 1,5 fois par oldCapacity

• Si la capacité dépasse MAX_ARRAY_SIZE, augmentez la capacité en fonction de MAX_ARRAY_SIZE

int newCapacity = oldCapacity + ((oldCapacity                                                              (ancienneCapacité + 2) :

              (ancienneCapacité >> ; 1));

PriorityQueue utilise 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. utilisateur Lors de l'insertion d'un objet de type personnalisé, vous devez fournir une classe de comparaison qui implémente l'interface Comparator et remplace la méthode de comparaison

// 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可
class IntCmp implements Comparator<Integer>{
   @Override
   public int compare(Integer o1, Integer o2) {
      return o2-o1;
   }
}
PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());

2、优先级队列的构造

构造器	功能介绍
PriorityQueue()	创建一个空的优先级队列，默认容量是11
PriorityQueue(int initialCapacity)	创建一个初始容量为initialCapacity的优先级队列，注意： initialCapacity不能小于1，否则会抛IllegalArgumentException异 常
PriorityQueue(Collection extends E> c)	用一个集合来创建优先级队列

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!