当前位置：网站首页>Tas (file d'attente prioritaire)

Tas (file d'attente prioritaire)

2022-07-02 12:07:00 【La nourriture n'est pas bonne.】

Table des matières

🥬La nature du tas

🥬Classification des piles

🥬Réglage vers le bas du tas

🥬Construction de piles

🥬Empiler vers le haut

🥬Opérations courantes du tas

Dans la file d'attente

Hors de la file d'attente

Obtenir l'élément chef d'équipe

🥬TopK Questions

🥬Résumé

🥬La nature du tas

Le tas est logiquement un arbre binaire complet,Le tas est physiquement stocké dans un tableau .

Résumé：UnArbre binaire completParTraversée séquentielle Comment stocker dans un tableau ,L'utilisation principale de cette méthode est la représentation du tas.

Et SiPère connu(parent)Indice,Et：

Enfant de gauche(left)Indice = 2 * parent + 1;

Enfant droit(right)Indice = 2 * parent + 2;

Les enfants connus（Pas de distinction entre gauche et droite）(child)Indice,Et：

Parents(parent)Indice = (child - 1) / 2;

🥬Classification des piles

Un tas de： Le noeud racine est plus grand que l'arbre binaire complet des deux noeuds enfants gauche et droit （ Le noeud parent est plus grand que son noeud Enfant ）,Ça s'appelle un tas de,Ou un gros tas de racines,Ou le plus gros tas .

Petit tas： Un arbre binaire complet dont le noeud racine est inférieur aux deux noeuds enfants gauche et droit s'appelle Petit tas（ Le noeud parent est plus petit que son noeud Enfant ）,Ou un petit tas de racines,Ou le plus petit tas.

🥬Réglage vers le bas du tas

Il y a maintenant un tableau, Logiquement, c'est un arbre binaire complet. ,On passe parNoeud racineAu débutAjustement vers le bas L'algorithme peut l'ajuster à un petit tas ou à un gros tas .L'algorithme de réglage vers le bas a une prémisse：Les sous - arbres gauche et droit doivent être un tas,Pour ajuster.

Prenons par exemple le petit tas：

1、 Comparez d'abord les noeuds gauche et droit de l'enfant ,Prenez le minimum.

2、 Comparez ce noeud enfant plus petit avec le noeud père , Si le noeud de l'enfant <Noeud père,Echange,Au contraire,Pas d'échange..

3、En boucle, Si l'indice du noeud enfant dépasse la limite , Ça veut dire que c'est la fin ,C'est fini..

Exemple de code：

 //parent: Noeud racine de chaque arbre
 //len: Position finale du réglage de chaque arbre

public void shiftDown(int parent,int len){
        int child=parent*2+1; //Parce que le tas est un arbre binaire complet,Pas d'enfant de gauche, pas d'enfant de droite, Donc au moins il y a un enfant de gauche ,Au moins.1Un enfant
        while(child<len){
            if(child+1<len && elem[child]<elem[child+1]){
                child++;// Les noeuds de deux enfants sont comparés à la valeur la plus faible 
            }
            if(elem[child]<elem[parent]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }

🥬Construction de piles

Donne un tableau,Ce tableau peut logiquement être considéré comme un arbre binaire complet,Mais ce n'est pas encore un tas（ Les sous - arbres de gauche et de droite sont pleins ou petits ）,Maintenant, nous passons par l'algorithme,Construire un tas（ Gros ou petit tas ）.Comment faire？Ici, nous commençons par ajuster le Sous - arbre du premier noeud non foliaire à l'envers,Arbre jusqu'au noeud racine,Vous pouvez ajuster les piles. Nous allons utiliser ce qui vient d'être écrit Ajustement vers le bas.

public void creatHeap(int[] arr){
        for(int i=0;i<arr.length;i++){
            elem[i]=arr[i];
            useSize++;
        }
        for(int parent=(useSize-1-1)/2;parent>=0;parent--){//Indice de tableau de0C'est parti.
            shiftDown(parent,useSize);
        }
    }

La complexité spatiale de la construction du réacteur est O（N）, Parce que le tas est un arbre binaire complet , Un arbre binaire plein est aussi un arbre binaire complet , Nous utilisons des arbres binaires （Dans le pire des cas）Pour prouver.

🥬Empiler vers le haut

Il y a une pile. , Nous devons insérer des données à la fin du tas , Et l'ajuster , Pour garder la structure du tas , C'est le réglage vers le haut .

Prenons l'exemple d'un tas de：

Exemple de code：

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

🥬Opérations courantes du tas

Dans la file d'attente

Ajouter des éléments au tas , Est d'ajouter à la dernière position , Ensuite, en faisant un ajustement vers le haut .

public boolean isFull(){
        return elem.length==useSize;
    }

public void offer(int val){
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);//Expansion de la capacité
        }
        elem[useSize++]=val;
        shiftup(useSize-1);
    }

Hors de la file d'attente

Supprimer les éléments du tas , En échange du dernier élément , Et puis réduire la taille du tableau entier d'un , Dernier ajustement vers le bas , L'élément supérieur de la pile est supprimé .

public boolean isEmpty(){
        return useSize==0;
    }

public int poll(){
        if(isEmpty()){
            throw new RuntimeException("La file d'attente prioritaire est vide");
        }
        int tmp=elem[0];
        elem[0]=elem[useSize-1];
        elem[useSize-1]=tmp;
        useSize--;
        shiftDown(0,useSize);
        return tmp;
    }

Obtenir l'élément chef d'équipe

public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("La file d'attente prioritaire est vide");
        }
        return elem[0];
    }

🥬TopK Questions

Voilà.6Données,S'il te plaît.3Maximum de données. Comment on fait avec les piles ？

Comment résoudre le problème：

1、Si je te le demandeKLes plus grands éléments,Pour construire un petit tas de racines.
2、Si je te le demandeKLes plus petits éléments,Pour construire un grand tas de racines.
3、NoKLes grands éléments.Construire un petit tas,L'élément supérieur de la pile estKLes grands éléments.
4、NoKPetits éléments.Construire un tas de,L'élément supérieur de la pile estKLes grands éléments.

Par exemple,：S'il te plaît.nMaximum de données

Exemple de code：

 public static int[] topK(int[] array,int k){
        //Créer une taille deKUn petit tas de racines
        PriorityQueue<Integer> minHeap=new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        //Traverser les éléments du tableau,AvantkÉléments mis en file d'attente
        for(int i=0;i<array.length;i++){
            if(minHeap.size()<k){
                minHeap.offer(array[i]);
            }else{
                //Dek+1Début des éléments, Comparer séparément avec les éléments supérieurs 
                int top=minHeap.peek();
                if(array[i]>top){
                    // Pop - up avant stockage 
                    minHeap.poll();
                    minHeap.offer(array[i]);
                }
            }
        }
        // Placer les éléments du tas dans le tableau 
        int[] tmp=new int[k];
        for(int i=0;i< tmp.length;i++){
            int top=minHeap.poll();
            tmp[i]=top;
        }
        return tmp;
    }

    public static void main(String[] args) {
        int[] array={12,8,23,6,35,22};
        int[] tmp=topK(array,3);
        System.out.println(Arrays.toString(tmp));
    }

Résultats：

Tri des tableaux

Encore une fois, si vous voulez trier un tableau de petit à grand , Avec un grand ou un petit tas de racines ？

---->Gros tas de racines

Exemple de code：

  public void heapSort(){
        int end=useSize-1;
        while(end>0){
            int tmp=elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            shiftDown(0,end);// Supposons qu'il s'agisse d'un grand tas de racines 
            end--;
        }
    }