简体中文(ZH-CN) English(EN) 繁体中文(ZH-TW) 日本語(JA) 한국어(KO) Melayu(MS) Français(FR) Deutsch(DE)
Maison > Java > javaDidacticiel > le corps du texte

Explication détaillée des principes et de la mise en œuvre du tas minimum et du tas maximum des structures de données Java

WBOY
Libérer： 2022-09-05 17:30:29
avant
2400 Les gens l'ont consulté

Cet article vous apporte des connaissances pertinentes sur java En informatique, l'implémentation du tas est une structure de données spéciale basée sur un arbre, qui peut construire une structure arborescente sur un tableau et satisfaire les propriétés du tas. sur le tas de la structure de données Java. Ceux qui sont intéressés peuvent en savoir plus.

Explication détaillée des principes et de la mise en œuvre du tas minimum et du tas maximum des structures de données Java

Étude recommandée : "Tutoriel vidéo Java"

1. Introduction

Histoire du tas

La structure des données du tas a de nombreuses formes, notamment 2-3 tas, tas B, binaire de Fibonacci ; tas, et le tas binaire le plus couramment utilisé dans l'API Java est le tas binaire utilisé pour implémenter les files d'attente prioritaires. Il a été introduit par JWJ Williams en 1964 en tant que structure de données pour l'algorithme de tri par tas. De plus, le tas est également très important dans plusieurs algorithmes de graphes efficaces tels que l'algorithme de Dijkstra.

2. Structure de données du tas

En informatique, l'implémentation du tas est une structure de données spéciale basée sur des arbres. Elle peut construire une structure arborescente sur un tableau et satisfaire les propriétés du tas

Tas minimum : Si P ; est un nœud parent de C, alors la clé (ou valeur) de P doit être inférieure ou égale à la valeur correspondante de C.

Max tas : Juste à l'opposé de la définition du min tas, dans max tas (max tas), la clé (ou valeur) de P est supérieure à la valeur correspondante de C.

3. Implémentation du code du tas

1. Introduction à l'implémentation

L'implémentation du tas dans l'API Java se reflète principalement dans l'implémentation du tas binaire de la file d'attente de retard. Ici, Brother Fu divise cette partie du code. Séparément, découvrez l'implémentation du petit tas et du grand tas.

Dès l'introduction à la structure des données du tas, nous pouvons voir que la seule différence entre un petit tas et un grand tas est la manière de trier les éléments. C'est-à-dire que la méthode de tri est différente lors du remplissage et de la suppression d'éléments lors du stockage et de la récupération d'éléments.

2. Implémentation du tas

Lors du stockage des éléments, le tas suit ses caractéristiques et sera migré vers le haut grâce à la comparaison des éléments de queue pendant le processus de stockage. 

private void siftUpComparable(int k, E x) {
    logger.info("【入队】元素：{} 当前队列：{}", JSON.toJSONString(x), JSON.toJSONString(queue));
    while (k > 0) {
        // 获取父节点Idx，相当于除以2
        int parent = (k - 1) >>> 1;
        logger.info("【入队】寻找当前节点的父节点位置。k：{} parent：{}", k, parent);
        Object e = queue[parent];
        // 如果当前位置元素，大于父节点元素，则退出循环
        if (compareTo(x, (E) e) >= 0) {
            logger.info("【入队】值比对，父节点：{} 目标节点：{}", JSON.toJSONString(e), JSON.toJSONString(x));
            break;
        }
        // 相反父节点位置大于当前位置元素，则进行替换
        logger.info("【入队】替换过程，父子节点位置替换，继续循环。父节点值：{} 存放到位置：{}", JSON.toJSONString(e), k);
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
    logger.info("【入队】完成 Idx：{} Val：{} \r\n当前队列：{} \r\n", k, JSON.toJSONString(x), JSON.toJSONString(queue));
}
Copier après la connexion

L'implémentation de l'ajout de la méthode add au tas finira par appeler la méthode siftUpComparable pour la traiter de manière triée. Cette méthode de tri compareTo est implémentée par MinHeap et MaxHeap spécifiques.

Prenons l'élément de tas 2 comme exemple, comme indiqué sur la figure.

Accrochez d'abord l'élément 2 à la fin de la file d'attente, puis calculez la position du nœud parent via (k - 1) >>>, comparez et jugez l'échange avec l'élément correspondant.

Le processus d'échange comprend 2->6, 2->5, après quoi les éléments sont enregistrés.

3. Implémenter des éléments

hors du tas est en fait très simple, il suffit de supprimer l'élément racine et de l'afficher directement. Mais les étapes restantes sont compliquées, car après la migration de l'élément racine, il est nécessaire de trouver un autre élément minimum à migrer vers l'extrémité opposée. Ce processus est exactement le contraire de l’entrée dans le tas. Il s’agit d’un processus de migration continue vers le bas. 

private void siftDownComparable(int k, E x) {
    // 先找出中间件节点
    int half = size >>> 1;
    while (k < half) {
        // 找到左子节点和右子节点，两个节点进行比较，找出最大的值
        int child = (k << 1) + 1;
        Object c = queue[child];
        int right = child + 1;
        // 左子节点与右子节点比较，取最小的节点
        if (right < size && compareTo((E) c, (E) queue[right]) > 0) {
            logger.info("【出队】左右子节点比对，获取最小值。left：{} right：{}", JSON.toJSONString(c), JSON.toJSONString(queue[right]));
            c = queue[child = right];
        }
        // 目标值与c比较，当目标值小于c值，退出循环。说明此时目标值所在位置适合，迁移完成。
        if (compareTo(x, (E) c) <= 0) {
            break;
        }
        // 目标值小于c值，位置替换，继续比较
        logger.info("【出队】替换过程，节点的值比对。上节点：{} 下节点：{} 位置替换", JSON.toJSONString(queue[k]), JSON.toJSONString(c));
        queue[k] = c;
        k = child;
    }
    // 把目标值放到对应位置
    logger.info("【出队】替换结果，最终更换位置。Idx：{} Val：{}", k, JSON.toJSONString(x));
    queue[k] = x;
}
Copier après la connexion

Migrez continuellement les éléments vers le bas. Ce processus comparera les valeurs des nœuds enfants gauche et droit et trouvera le plus petit. L’ensemble du processus sera donc plus fastidieux que l’entrée dans la pile.

Ici, nous prenons l'élément pop-up 1 comme exemple, puis remplaçons l'élément à la fin du tas à la position correspondante. L'ensemble du processus est divisé en 6 images.

  • Figure 1 à Figure 2, recherchez l'élément racine à afficher.
  • De la figure 3 à la figure 4, déplacez l'élément racine vers le bas, comparez-le avec les éléments enfants et remplacez la position. Si cette position est comparée à 8 et est inférieure à 8, elle continuera à migrer vers le bas.
  • De la Figure 4 à la Figure 5, continuez la migration. Les deux sous-éléments correspondant à la position du nœud d'origine 4 sont tous deux plus grands que 8. Vous pouvez arrêter à ce moment.
  • Figure 5 à Figure 6, changez la position de l'élément, remplacez l'élément en fin de file d'attente à la position correspondant à la détection de migration vers le bas de l'élément 1.

4. Implémentation d'un petit tas

Un petit tas est une comparaison de séquence positive

public class MinHeap extends Heap<Integer> {

    @Override
    public int compareTo(Integer firstElement, Integer secondElement) {
        return firstElement.compareTo(secondElement);
    }

}
Copier après la connexion

Test

@Test
public void test_min_heap() {
    MinHeap heap = new MinHeap();
    // 存入元素
    heap.add(1);
    heap.add(3);
    heap.add(5);
    heap.add(11);
    heap.add(4);
    heap.add(6);
    heap.add(7);
    heap.add(12);
    heap.add(15);
    heap.add(10);
    heap.add(9);
    heap.add(8);
    // 弹出元素
    while (heap.peek() != null){
        logger.info("测试结果：{}", heap.poll());
    }
}
Copier après la connexion

Résultat

17:21:30.053 [main] INFO queue.PriorityQueue - [Enqueue] Élément : 3 File d'attente actuelle : [1,null,null,null,null,null,null,null,null,null,null]
17 : 21:30.055 [main] INFO queue.PriorityQueue - [Enqueue] Recherchez la position du nœud parent du nœud actuel. k : 1 parent : 0
17:21:30.056 [principal] INFO queue.PriorityQueue - [Entrer la file d'attente] comparaison de valeurs, nœud parent : 1 nœud cible : 3
17:21:30.056 [principal] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Terminé Idx : 1 Val : 3
File d'attente actuelle : [1,3,null,null,null,null,null,null,null,null,null]

17:21:30.056 [principale] File d'attente INFO .PriorityQueue - [Enqueue] Élément : 5 File d'attente actuelle : [1,3,null,null,null,null,null,null,null,null,null]
17:21:30.056 [principale] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 2 parent : 0
17:21:30.056 [principal] INFO queue.PriorityQueue - [Entrer la file d'attente] Comparaison de valeurs, nœud parent : 1 Nœud cible : 5
17:21:30.056 [main] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Terminé Idx : 2 Val : 5
File d'attente actuelle : [1,3,5,null,null,null,null,null,null,null,null]

17:21:30.056 [principale] File d'attente INFO .PriorityQueue - [Entrer la file d'attente] Élément : 11 File d'attente actuelle : [1,3,5,null,null,null,null,null,null,null,null]
17:21:30.056 [principale] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 3 parent : 1
17:21:30.056 [principal] INFO queue.PriorityQueue - [Entrer la file d'attente] comparaison de valeurs, nœud parent : 3 nœud cible : 11
17:21:30.056 [main] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Idx terminé : 3 Val : 11
File d'attente actuelle : [1,3,5,11,null,null,null,null,null,null,null]

17:21:30.056 [principale] File d'attente INFO .PriorityQueue - [Entrer la file d'attente] Élément : 4 File d'attente actuelle : [1,3,5,11,null,null,null,null,null,null,null]
17:21:30.056 [principale] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 4 parent : 1
17:21:30.056 [principal] INFO queue.PriorityQueue - [Entrer la file d'attente] comparaison de valeurs, nœud parent : 3 nœud cible : 4
17:21:30.056 [principal] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Terminé Idx : 4 Val : 4
File d'attente actuelle : [1,3,5,11,4,null,null,null,null,null,null]

17:21:30.056 [principale] File d'attente INFO .PriorityQueue - [Entrer la file d'attente] Éléments : 6 File d'attente actuelle : [1,3,5,11,4,null,null,null,null,null,null]
17:21:30.056 [principale] File d'attente INFO.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 5 parent : 2
17:21:30.056 [principal] INFO queue.PriorityQueue - [Entrer la file d'attente] comparaison de valeurs, nœud parent : 5 nœud cible : 6
17:21:30.056 [principal] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Terminé Idx : 5 Val : 6
File d'attente actuelle : [1,3,5,11,4,6,null,null,null,null,null]

17:21:30.056 [principale] File d'attente INFO .PriorityQueue - [Entrer la file d'attente] Élément : 7 File d'attente actuelle : [1,3,5,11,4,6,null,null,null,null,null]
17:21:30.056 [principale] File d'attente INFO.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 6 parent : 2
17:21:30.056 [principal] INFO queue.PriorityQueue - [Entrer la file d'attente] comparaison de valeurs, nœud parent : 5 nœud cible : 7
17:21:30.056 [principal] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Terminé Idx : 6 Val : 7
File d'attente actuelle : [1,3,5,11,4,6,7,null,null,null,null] 17:21:30.056 [principale] File d'attente INFO.PriorityQueue - [Enter Queue] Élément : 12 File d'attente actuelle : [1,3,5,11,4,6,7,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - [Enter Team] Recherchez la position du nœud parent du nœud actuel. k : 7 parent : 3
17:21:30.056 [principal] INFO queue.PriorityQueue - [Entrer la file d'attente] comparaison de valeurs, nœud parent : 11 nœud cible : 12
17:21:30.056 [main] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Terminé Idx : 7 Val : 12
File d'attente actuelle : [1,3,5,11,4,6,7,12,null,null,null]

17:21:30.056 [principale] File d'attente INFO .PriorityQueue - [Enqueue] Élément : 15 File d'attente actuelle : [1,3,5,11,4,6,7,12,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 8 parent : 3
17:21:30.056 [principal] INFO queue.PriorityQueue - [Entrer la file d'attente] comparaison de valeurs, nœud parent : 11 nœud cible : 15
17:21:30.057 [main] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Terminé Idx : 8 Val : 15
File d'attente actuelle : [1,3,5,11,4,6,7,12,15,null,null]

17:21:30.057 [principale] File d'attente INFO .PriorityQueue - [Enqueue] Éléments : 10 File d'attente actuelle : [1,3,5,11,4,6,7,12,15,null,null]
17:21:30.057 [principale] File d'attente INFO.PriorityQueue - [ Entrez dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 9 parent : 4
17:21:30.057 [principal] INFO queue.PriorityQueue - [Entrer la file d'attente] comparaison de valeurs, nœud parent : 4 nœud cible : 10
17:21:30.057 [principal] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Terminé Idx : 9 Val : 10
File d'attente actuelle : [1,3,5,11,4,6,7,12,15,10,null]

17:21:30.057 [principale] File d'attente INFO .PriorityQueue - [Enqueue] Élément : 9 File d'attente actuelle : [1,3,5,11,4,6,7,12,15,10,null]
17:21:30.057 [principale] File d'attente INFO.PriorityQueue - [ Entrez dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k：10 parent：4
17:21:30.057 [principal] INFO queue.PriorityQueue - [Enter Queue] Comparaison de valeurs, nœud parent : 4 Nœud cible : 9
17:21:30.057 [principal] INFO queue.PriorityQueue - [Enter Queue] Achèvement Idx : 10 Val : 9
File d'attente actuelle : [1,3,5,11,4,6,7,12,15,10,9]

17:21:30.057 [principale] File d'attente INFO.PriorityQueue - [Entrer la file d'attente] Éléments : 8 File d'attente actuelle : [1,3,5,11,4,6,7,12,15,10,9,null,null,null,null,null,null,null,null,null,null,null , null,null]
17:21:30.057 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 11 parent : 5
17:21:30.057 [principal] INFO queue.PriorityQueue - [Entrer la file d'attente] comparaison de valeurs, nœud parent : 6 nœud cible : 8
17:21:30.057 [main] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Terminé Idx : 11 Val : 8
File d'attente actuelle : [1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null, null,null,null,null,null,null,null]

17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison des valeurs de nœud. Nœud supérieur : 1 Nœud inférieur : 3 Remplacement de position
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Comparez les nœuds enfants gauche et droit pour obtenir la valeur minimale. gauche : 11 droite : 4
17:21:30.057 [main] INFO queue.PriorityQueue - Processus de remplacement [Dequeue], comparaison des valeurs de nœud. Nœud supérieur : 3 Nœud inférieur : 4 Remplacement de position
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Comparez les nœuds enfants gauche et droit pour obtenir la valeur minimale. gauche : 10 droite : 9
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Remplacez le résultat et enfin changez la position. Idx : 4 Val : 8
17:21:30.057 [main] INFO heap.__test__.HeapTest - Résultat du test : 1
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, valeur du nœud Comparer. Nœud supérieur : 3 Nœud inférieur : 4 Remplacement de position
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Comparez les nœuds enfants gauche et droit pour obtenir la valeur minimale. gauche : 11 droite : 8
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison des valeurs de nœud. Nœud supérieur : 4 Nœud inférieur : 8 Remplacement de position
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Remplacez le résultat et enfin changez la position. Idx : 4 Val : 9
17:21:30.057 [main] INFO heap.__test__.HeapTest - Résultat du test : 3
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Comparaison des nœuds enfants gauche et droit , Obtenez la valeur minimale. gauche : 8 droite : 5
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] processus de remplacement, comparaison des valeurs de nœud. Nœud supérieur : 4 Nœud inférieur : 5 Remplacement de position
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison des valeurs du nœud. Nœud supérieur : 5 Nœud inférieur : 6 Remplacement de position
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Remplacez le résultat et enfin changez la position. Idx : 5 Val : 10
17:21:30.057 [main] INFO heap.__test__.HeapTest - Résultat du test : 4
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Comparaison des nœuds enfants gauche et droit , Obtenez la valeur minimale. gauche : 8 droite : 6
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison des valeurs de nœud. Nœud supérieur : 5 Nœud inférieur : 6 Remplacement de position
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Comparez les nœuds enfants gauche et droit pour obtenir la valeur minimale. gauche : 10 droite : 7
17:21:30.058 [main] INFO queue.PriorityQueue - Processus de remplacement [Dequeue], comparaison des valeurs de nœud. Nœud supérieur : 6 Nœud inférieur : 7 Remplacement de position
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Remplacez le résultat et enfin changez la position. Idx : 6 Val : 15
17:21:30.058 [main] INFO heap.__test__.HeapTest - Résultat du test : 5
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Comparaison des nœuds enfants gauche et droit , Obtenez la valeur minimale. gauche : 8 droite : 7
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] processus de remplacement, comparaison des valeurs de nœud. Nœud supérieur : 6 Nœud inférieur : 7 Remplacement de position
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison des valeurs du nœud. Nœud supérieur : 7 Nœud inférieur : 10 Remplacement de position
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Remplacez le résultat et enfin changez la position. Idx : 5 Val : 12
17:21:30.058 [main] INFO heap.__test__.HeapTest - Résultat du test : 6
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison de la valeur du nœud. Nœud supérieur : 7 Nœud inférieur : 8 Remplacement de position
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Comparez les nœuds enfants gauche et droit pour obtenir la valeur minimale. gauche : 11 droite : 9
17:21:30.058 [main] INFO queue.PriorityQueue - Processus de remplacement [Dequeue], comparaison des valeurs de nœud. Nœud supérieur : 8 Nœud inférieur : 9 Remplacement de position
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Remplacez le résultat et enfin changez la position. Idx : 4 Val : 15
17:21:30.058 [main] INFO heap.__test__.HeapTest - Résultat du test : 7
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison de la valeur du nœud. Nœud supérieur : 8 Nœud inférieur : 9 Remplacement de position
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison des valeurs du nœud. Nœud supérieur : 9 Nœud inférieur : 11 Remplacement de position
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：3 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：8
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：11 right：10
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：9 下节点：10 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：2 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：9
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：10 下节点：11 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：1 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：10
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：11 下节点：12 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：1 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：11
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：0 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：15

Process finished with exit code 0
小堆就是一个正序的输出结果，从小到大的排序和输出。
小堆空间：[1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null,null,null,null,null,null,null,null]

  • 小堆就是一个正序的输出结果，从小到大的排序和输出。
  • 小堆空间：[1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null,null,null,null,null,null,null,null]

5. 大堆实现

小堆是一个反序比对

public class MaxHeap extends Heap<Integer> {

    @Override
    public int compareTo(Integer firstElement, Integer secondElement) {
        return secondElement.compareTo(firstElement);
    }

}
Copier après la connexion

测试

@Test
public void test_max_heap() {
    MaxHeap heap = new MaxHeap();
    // 存入元素
    heap.add(1);
    heap.add(3);
    heap.add(5);
    heap.add(11);
    heap.add(4);
    heap.add(6);
    heap.add(7);
    heap.add(12);
    heap.add(15);
    heap.add(10);
    heap.add(9);
    heap.add(8);
    // 弹出元素
    while (heap.peek() != null){
        logger.info("测试结果：{}", heap.poll());
    }
}
Copier après la connexion

结果

17:23:45.079 [main] INFO queue.PriorityQueue - [Enqueue] Élément : 3 File d'attente actuelle : [1,null,null,null,null,null,null,null,null,null,null]
17 : 23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] Recherchez la position du nœud parent du nœud actuel. k : 1 parent : 0
17:23:45.081 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Processus de remplacement, la position des nœuds parent et enfant est remplacée et le cycle continue. Valeur du nœud parent : 1 Stocké en position : 1
17:23:45.081 [main] INFO queue.PriorityQueue - [Entrer la file d'attente] Idx terminé : 0 Val : 3
File d'attente actuelle : [3,1,null,null,null, null,null,null,null,null,null]

17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] Élément : 5 File d'attente actuelle : [3,1,null,null,null,null, null ,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 2 parent : 0
17:23:45.081 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Processus de remplacement, la position des nœuds parent et enfant est remplacée et le cycle continue. Valeur du nœud parent : 3 Stocké en position : 2
17:23:45.081 [main] INFO queue.PriorityQueue - [Entrer la file d'attente] Idx terminé : 0 Val : 5
File d'attente actuelle : [5,1,3,null,null, null,null,null,null,null,null]

17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] Élément : 11 File d'attente actuelle : [5,1,3,null,null,null, null ,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 3 parent : 1
17:23:45.081 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Processus de remplacement, la position des nœuds parent et enfant est remplacée et le cycle continue. Valeur du nœud parent : 1 Stocké à l'emplacement : 3
17:23:45.081 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 1 parent : 0
17:23:45.081 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Processus de remplacement, la position des nœuds parent et enfant est remplacée et le cycle continue. Valeur du nœud parent : 5 Stocké en position : 1
17:23:45.081 [main] INFO queue.PriorityQueue - [Entrer la file d'attente] Idx terminé : 0 Val : 11
File d'attente actuelle : [11,5,3,1,null, null,null,null,null,null,null]

17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] Élément : 4 File d'attente actuelle : [11,5,3,1,null,null, null ,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 4 parent : 1
17:23:45.082 [principal] INFO queue.PriorityQueue - [Entrer la file d'attente] comparaison de valeurs, nœud parent : 5 nœud cible : 4
17:23:45.082 [principal] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Terminé Idx : 4 Val : 4
File d'attente actuelle : [11,5,3,1,4,null,null,null,null,null,null]

17:23:45.082 [principale] File d'attente INFO .PriorityQueue - [Enqueue] Élément : 6 File d'attente actuelle : [11,5,3,1,4,null,null,null,null,null,null]
17:23:45.082 [principale] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 5 parent : 2
17:23:45.082 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Processus de remplacement, la position des nœuds parent et enfant est remplacée et le cycle continue. Valeur du nœud parent : 3 Stocké à l'emplacement : 5
17:23:45.082 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 2 parent : 0
17:23:45.082 [principal] INFO queue.PriorityQueue - [Entrer la file d'attente] Comparaison de valeurs, nœud parent : 11 Nœud cible : 6
17:23:45.082 [main] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Terminé Idx : 2 Val : 6
File d'attente actuelle : [11,5,6,1,4,3,null,null,null,null,null]

17:23:45.082 [principale] File d'attente INFO .PriorityQueue - [Enter queue] Élément : 7 File d'attente actuelle : [11,5,6,1,4,3,null,null,null,null,null]
17:23:45.082 [principale] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 6 parent : 2
17:23:45.082 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Processus de remplacement, la position des nœuds parent et enfant est remplacée et le cycle continue. Valeur du nœud parent : 6 Stocké dans la position : 6
17:23:45.082 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 2 parent : 0
17:23:45.082 [principal] INFO queue.PriorityQueue - [Entrer la file d'attente] Comparaison de valeurs, nœud parent : 11 Nœud cible : 7
17:23:45.082 [main] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Terminé Idx : 2 Val : 7
File d'attente actuelle : [11,5,7,1,4,3,6,null,null,null,null]

17:23:45.082 [principale] File d'attente INFO .PriorityQueue - [Enter queue] Élément : 12 File d'attente actuelle : [11,5,7,1,4,3,6,null,null,null,null]
17:23:45.082 [principale] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 7 parent : 3
17:23:45.082 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Processus de remplacement, la position des nœuds parent et enfant est remplacée et le cycle continue. Valeur du nœud parent : 1 Stocké dans la position : 7
17:23:45.082 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 3 parent : 1
17:23:45.082 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Processus de remplacement, la position des nœuds parent et enfant est remplacée et le cycle continue. Valeur du nœud parent : 5 Stocké à l'emplacement : 3
17:23:45.082 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k：1 parent：0
17:23:45.082 [main] INFO queue.PriorityQueue - [Mise en file d'attente] Processus de remplacement, la position des nœuds parent et enfant est remplacée et le cycle continue. Valeur du nœud parent : 11 Stocké en position : 1
17:23:45.082 [main] INFO queue.PriorityQueue - [Entrer la file d'attente] Idx terminé : 0 Val : 12
File d'attente actuelle : [12,11,7,5,4, 3,6,1,null,null,null]

17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] Élément : 15 File d'attente actuelle : [12,11,7,5,4,3, 6 ,1,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 8 parent : 3
17:23:45.082 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Processus de remplacement, la position des nœuds parent et enfant est remplacée et le cycle continue. Valeur du nœud parent : 5 Stocké à l'emplacement : 8
17:23:45.082 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 3 parent : 1
17:23:45.082 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Processus de remplacement, la position des nœuds parent et enfant est remplacée et le cycle continue. Valeur du nœud parent : 11 Stocké dans la position : 3
17:23:45.082 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 1 parent : 0
17:23:45.082 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Processus de remplacement, la position des nœuds parent et enfant est remplacée et le cycle continue. Valeur du nœud parent : 12 Stocké en position : 1
17:23:45.082 [main] INFO queue.PriorityQueue - [Entrer la file d'attente] Idx terminé : 0 Val : 15
File d'attente actuelle : [15,12,7,11,4, 3,6,1,5,null,null]

17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] Élément : 10 File d'attente actuelle : [15,12,7,11,4,3, 6 ,1,5,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 9 parent : 4
17:23:45.083 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Processus de remplacement, la position des nœuds parent et enfant est remplacée et le cycle continue. Valeur du nœud parent : 4 Stocké à l'emplacement : 9
17:23:45.083 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 4 parent : 1
17:23:45.083 [principal] INFO queue.PriorityQueue - [Entrer la file d'attente] Comparaison de valeurs, nœud parent : 12 Nœud cible : 10
17:23:45.083 [main] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Terminé Idx : 4 Val : 10
File d'attente actuelle : [15,12,7,11,10,3,6,1,5,4,null]

17:23:45.083 [principale] File d'attente INFO .PriorityQueue - [Enqueue] Élément : 9 File d'attente actuelle : [15,12,7,11,10,3,6,1,5,4,null]
17:23:45.083 [principale] File d'attente INFO.PriorityQueue - [ Entrez dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 10 parent : 4
17:23:45.083 [principal] INFO queue.PriorityQueue - [Entrer la file d'attente] comparaison de valeurs, nœud parent : 10 nœud cible : 9
17:23:45.083 [principal] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Terminé Idx : 10 Val : 9
File d'attente actuelle : [15,12,7,11,10,3,6,1,5,4,9]

17:23:45.083 [principale] File d'attente INFO .PriorityQueue - Élément [Enqueue] : 8 File d'attente actuelle : [15,12,7,11,10,3,6,1,5,4,9,null,null,null,null,null,null,null, null ,null,null,null,null,null]
17:23:45.083 [main] INFO queue.PriorityQueue - [Mise en file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 11 parent : 5
17:23:45.083 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Processus de remplacement, la position des nœuds parent et enfant est remplacée et le cycle continue. Valeur du nœud parent : 3 Stocké à l'emplacement : 11
17:23:45.083 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 5 parent : 2
17:23:45.083 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Processus de remplacement, la position des nœuds parent et enfant est remplacée et le cycle continue. Valeur du nœud parent : 7 Stocké à l'emplacement : 5
17:23:45.083 [main] INFO queue.PriorityQueue - [Entrer dans la file d'attente] Recherchez la position du nœud parent du nœud actuel. k : 2 parent : 0
17:23:45.083 [principal] INFO queue.PriorityQueue - [Entrer la file d'attente] comparaison de valeurs, nœud parent : 15 nœud cible : 8
17:23:45.083 [principal] INFO queue.PriorityQueue - [ Entrez dans la file d'attente] Idx terminé : 2 Val : 8
File d'attente actuelle : [15,12,8,11,10,7,6,1,5,4,9,3,null,null,null,null,null, null,null,null,null,null,null,null]

17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison des valeurs de nœud. Nœud supérieur : 15 Nœud inférieur : 12 Remplacement de position
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison des valeurs de nœud. Nœud supérieur : 12 Nœud inférieur : 11 Remplacement de position
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Comparez les nœuds enfants gauche et droit pour obtenir la valeur minimale. gauche : 1 droite : 5
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison des valeurs de nœud. Nœud supérieur : 11 Nœud inférieur : 5 Remplacement de position
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Remplacez le résultat et enfin changez la position. Idx : 8 Val : 3
17:23:45.083 [main] INFO heap.__test__.HeapTest - Résultat du test : 15
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, valeur du nœud Comparer. Nœud supérieur : 12 Nœud inférieur : 11 Remplacement de position
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Comparez les nœuds enfants gauche et droit pour obtenir la valeur minimale. gauche ： 5 droite ： 10
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison des valeurs de nœud. Nœud supérieur : 11 Nœud inférieur : 10 Remplacement de position
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Remplacez le résultat et enfin changez la position. Idx : 4 Val : 9
17:23:45.083 [main] INFO heap.__test__.HeapTest - Résultat du test : 12
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison de la valeur du nœud. Nœud supérieur : 11 Nœud inférieur : 10 Remplacement de position
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Comparez les nœuds enfants gauche et droit pour obtenir la valeur minimale. gauche : 5 droite : 9
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison des valeurs de nœud. Nœud supérieur : 10 Nœud inférieur : 9 Remplacement de position
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Remplacez le résultat et enfin changez la position. Idx : 4 Val : 4
17:23:45.083 [main] INFO heap.__test__.HeapTest - Résultat du test : 11
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison de la valeur du nœud. Nœud supérieur : 10 Nœud inférieur : 9 Remplacement de position
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison des valeurs du nœud. Nœud supérieur : 9 Nœud inférieur : 5 Remplacement de position
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Remplacez le résultat et enfin changez la position. Idx : 3 Val : 3
17:23:45.084 [main] INFO heap.__test__.HeapTest - Résultat du test : 10
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Comparaison des nœuds enfants gauche et droit , Obtenez la valeur minimale. gauche : 5 droite : 8
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison des valeurs de nœud. Nœud supérieur : 9 Nœud inférieur : 8 Remplacement de position
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison des valeurs de nœud. Nœud supérieur : 8 Nœud inférieur : 7 Remplacement de position
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Remplacez le résultat et enfin changez la position. Idx : 5 Val : 1
17:23:45.084 [main] INFO heap.__test__.HeapTest - Résultat du test : 9
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Comparaison des nœuds enfants gauche et droit , Obtenez la valeur minimale. gauche : 5 droite : 7
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison des valeurs de nœud. Nœud supérieur : 8 Nœud inférieur : 7 Remplacement de position
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Remplacez le résultat et enfin changez la position. Idx : 2 Val : 6
17:23:45.084 [main] INFO heap.__test__.HeapTest - Résultat du test : 8
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Comparaison des nœuds enfants gauche et droit , Obtenez la valeur minimale. gauche : 5 droite : 6
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, comparaison des valeurs de nœud. Nœud supérieur : 7 Nœud inférieur : 6 Remplacement de position
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Remplacez le résultat et enfin changez la position. Idx : 2 Val : 1
17:23:45.084 [main] INFO heap.__test__.HeapTest - Résultat du test : 7
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, valeur du nœud Comparer. Nœud supérieur : 6 Nœud inférieur : 5 Remplacement de position
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Remplacez le résultat et enfin changez la position. Idx : 1 Val : 4
17:23:45.084 [main] INFO heap.__test__.HeapTest - Résultat du test : 6
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, valeur du nœud Comparer. Nœud supérieur : 5 Nœud inférieur : 4 Remplacement de position
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Remplacez le résultat et enfin changez la position. Idx : 1 Val : 3
17:23:45.084 [main] INFO heap.__test__.HeapTest - Résultat du test : 5
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Processus de remplacement, valeur du nœud Comparer. Nœud supérieur : 4 Nœud inférieur : 3 Remplacement de position
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Remplacez le résultat et enfin changez la position. Idx : 1 Val : 1
17:23:45.084 [main] INFO heap.__test__.HeapTest - Résultat du test : 4
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Résultat de remplacement, position de remplacement finale. Idx : 0 Val : 1
17:23:45.084 [main] INFO heap.__test__.HeapTest - Résultat du test : 3
17:23:45.084 [main] INFO heap.__test__.HeapTest - Résultat du test : 1

Processus terminé avec le code de sortie 0

Le gros tas est le résultat de sortie dans l'ordre inverse, trié et sorti du plus grand au plus petit.

Grand espace : [15,12,8,11,10,7,6,1,5,4,9,3,null,null,null,null,null,null,null,null,null,null, null,null]

Apprentissage recommandé : "Tutoriel vidéo Java"

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!

Étiquettes associées：
java
source：jb51.net
Article précédent：Tutoriel de développement de sites Web dynamiques Java Web Article suivant：Parlons de l'encapsulation Java, de l'héritage et des fonctionnalités polymorphes
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Derniers articles par auteur
Derniers numéros
Comment convertir une chaîne en un nombre à 19 chiffres en javaScript sans arrondi automatique ? Nous avons une entrée de chaîne number input="6145390195186705543" si nous voulo...
Depuis 2024-03-30 14:42:35
0
1
367
Rubriques connexes
Plus>
Recommandations populaires
Tutoriels populaires
Plus>
Tutoriels associés
Recommandations populaires
Derniers cours
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal
À propos de nous Clause de non-responsabilité Sitemap
Site Web PHP chinois：Formation PHP en ligne sur le bien-être public，Aidez les apprenants PHP à grandir rapidement！