Tas - Min et Max

Tas - Tas minimum

Heap est une version plus efficace de la liste des priorités. Prendre en compte les méthodes d'insertion et de suppression de la File d'attente prioritaire Triée et Non triée, dans Coûts d'insertion non triés O(1), en supprimant les coûts O(n), tandis que Coûts d'insertion triés O(n) et supprimant O(1).

	sorted	unsorted
insert	O(n)	O(1)
remove	O(1)	O(n)

Le tas est construit par un Array, mais sa représentation est un arbre binaire, l'élément avec le plus de priorité est en haut, la racine. Il est rempli de haut en bas et de droite à gauche, sans qu'aucun enfant ne manque !

?

Cependant, il existe la possibilité de construire la structure de données avec la priorité la plus élevée étant définie par la valeur clé la plus élevée. Dans ce cas, nous avons le tas maximum, que nous verrons plus tard.

Min_Heap

Pour être un tas valide, tous les éléments enfants doivent avoir une priorité inférieure ou égale à celle de leurs parents. De plus, il doit être complet sans enfants manquants, sinon le tableau aura un espace vide.

?

Une manière plus formelle de réaliser cette définition est de dire qu'un arbre binaire est complet si ses niveaux 0, 1, 2, · · · h − 1 ont le maximum d'éléments possibles et les éléments existant au niveau h sont alloués le plus à gauche possible.

Comme mentionné, le tas est constitué d'un tableau (représenté en vert), mais peut être visualisé comme une structure arborescente, comme le montre l'image ci-dessous.

Il existe deux manières d'assembler le Heap, avec le premier élément en position 0, ou sans position 0, dans cet article nous verrons la différence entre les deux cas. Les éléments du haut ont toujours leurs enfants, communément appelés éléments du bas, pour découvrir ces enfants, dans le cas de l'indice 0, vous pouvez obtenir cette information grâce à ces calculs :

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

Si vous utilisez une version avec 0 non renseigné, réduisez simplement la somme, c'est-à-dire 1-1=0, dans le cas parent c'est index / 2.

Insérer

Il est toujours ajouté à la fin, la seule préoccupation que vous devriez avoir est de vérifier si l'élément enfant a une clé inférieure à celle du parent, à cet effet un bouillonnement est effectué, c'est-à-dire lorsque les clés de l'élément inséré sont comparé et le père, en changeant si nécessaire.

Pour parler plus en détail, placez l'élément dans le dernier espace vide de l'arbre et, comme il faut comparer sa clé avec celle du parent, il faut calculer l'index du parent pour accéder à sa clé. Pour connaître le père, utilisez le calcul mentionné :

parent = (indexDoFilho -1)/2

Et pour cela, il manque l'indexDoFilho : pour l'obtenir, on prend une variable pour être l'index courant, comme on est dans l'insert qui est une addition à la fin, l'index courant est le dernier, soit :

currentIndex = size-1

Maintenant que vous avez l'index actuel, appelez Parent et découvrez qui est le père de l'élément en cours d'insertion. Nous voulons le parent de ce nouvel élément car, pour organiser correctement l'arborescence, cet élément doit être comparé à son parent et, si sa clé est plus petite, ils doivent échanger leurs emplacements.

Tant que l'index actuel est supérieur à 0 (afin d'éviter de récupérer un index indisponible) et que l'index actuel est plus petit que l'index du parent, si cette condition est vraie, l'élément doit être échangé avec le parent pour garantir la propriété du tas minimum, puis l'échange se produit, puis l'index actuel reçoit l'index du parent, puis prend le parent du parent (KKKKK) pour . Le swap est une méthode qui utilise la structure d'un échange normal de valeurs.

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

Être apparenté :

parent = (indexDoFilho -1)/2

Le swap étant une méthode normale d'échange de valeurs :

currentIndex = size-1

Si la valeur de l'élément actuel (enfant) est inférieure à la valeur du parent, cela indique que la propriété minimum du tas a été violée. Dans un tas minimal, le parent doit toujours être inférieur ou égal à l'enfant. Lorsque cette condition n'est pas remplie, l'enfant doit échanger sa place avec le parent pour que la plus petite valeur continue de "grimper" dans le tas jusqu'à trouver la bonne position, où la propriété sera conservée.

Retirer

Supprime l'élément d'index 0, mais l'arborescence n'est plus complète ! Pour résoudre ce problème, tirez le dernier élément du tableau vers le début, c'est-à-dire que le dernier élément ajouté va en haut de l'arborescence. Après cela, vérifiez à nouveau, mais maintenant de haut en bas. Autrement dit, c’est le moment de comparer les parents avec leurs enfants ! (affaissement)
La méthode SinkDown() déplace l'élément vers le bas (ou « coule ») dans le tas, jusqu'à ce qu'il soit dans la position correcte, où sa valeur est inférieure ou égale à celle de ses enfants (s'il est dans une position avec des enfants) .
Dans SinkDown, il existe une variable pour stocker l'index de l'élément avec la clé la plus basse commençant à la racine et une autre pour l'index actuel. Ensuite, une boucle qui durera jusqu'à ce que l'index de l'élément courant soit égal à l'index de l'élément de clé la plus basse. À l'intérieur de la boucle, récupérez les enfants de la boucle actuelle et voyez si les enfants sont dans la plage du tableau et si l'index de l'enfant est inférieur à l'index minimum, il met à jour le minimum.

public void insert(K key, V value) { //o(log n)
    if (isFull()){
        throw new RuntimeException("full");
    }
    //adc a entry na ultima posição do vetor
    heap[size++]=new PriorityEntry(key, value);
    //guarda o index que esse novo elemento tá
    int currentIndex = size-1;
    //chama o método parent pra calcular quem é o pai do novo elemento
    int parent = parent(currentIndex);
    //percorre enquanto o index nao for o 0 e o index ser 
    while (currentIndex>0 && compare(currentIndex, parent)<0){
        swap(currentIndex, parent);
        currentIndex = parent;
        parent = parent(currentIndex);
    }
}

Dans ce cas :

protected int parent(int index){
        return (index-1)/2;
}

Résumé:

Propriétés minimales du tas :

• Structure arborescente binaire complète.
• Le nœud parent a toujours une valeur égale ou inférieure à celle de ses nœuds enfants.
• Implémenté via un tableau, où la position des enfants et des parents est déterminée par des formules basées sur l'index.

Pour calculer les positions des enfants et des parents :

• Gauche : leftChild = index * 2 1
• Droite : rightChild = index * 2 2
• Parent : parent = (index - 1) / 2

Version sans index 0 : Soustrayez simplement 1 des calculs, ce qui donne :

• leftChild = index * 2
• rightChild = index * 2 1
• parent = indice / 2

Tas - Tas maximum

La valeur la plus élevée est à la racine, donc le nœud parent a une valeur égale ou supérieure à celle de ses enfants

Les formules de calcul des enfants et des parents :

• Gauche : leftChild = index * 2 1
• Droite : rightChild = index * 2 2
• Parent : parent = (index - 1) / 2

Insérer

Ajoute l'élément à la fin et bouillonne, ce qui consisterait à comparer l'élément avec son parent, en changeant d'emplacement si nécessaire. O(log n).

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

Retirer

Supprime l'élément heapMax[0], alias la racine, puis prend le dernier élément et le déplace vers la racine, appelant Sinkdown puis poussant le nouvel élément de la racine vers le bas jusqu'à ce qu'il trouve sa position correcte.

sinkDown doit s'assurer que la valeur dans le nœud parent est supérieure ou égale à les valeurs dans les nœuds enfants. Par conséquent, lors de l'immersion d'un nœud, il sera comparé au le plus grand enfant.

Dans le Min Heap, SinkDown doit s'assurer que la valeur dans le nœud parent est inférieure ou égale à les valeurs des enfants. Dans ce cas, la comparaison est faite avec le enfant le plus petit.

parent = (indexDoFilho -1)/2

currentIndex = size-1

Différences

• Dans Max Heap, SinkDown doit s'assurer que la valeur dans le nœud parent est supérieure ou égale à les valeurs dans les nœuds enfants. Par conséquent, lors de l'immersion d'un nœud, il sera comparé au le plus grand enfant.
• Dans Max Heap, si le nœud parent est plus petit que le plus grand de ses enfants, alors il doit échanger avec le plus grand enfant pour garantir que la plus grande valeur est aussi élevée que possible.
• Dans le Min Heap, SinkDown doit s'assurer que la valeur dans le nœud parent est inférieure ou égale à les valeurs des enfants. Dans ce cas, la comparaison est faite avec le enfant le plus petit.
• Dans le Min Heap, la commutation se produit si le nœud parent est supérieur au plus petit des enfants, en gardant la plus petite valeur en haut

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!