Stockage de base du tas

Concept et introduction

Le tas est un terme général désignant une classe spéciale de structures de données en informatique.

Un tas est généralement un objet de type tableau qui peut être considéré comme un arbre binaire complet.

Un tas satisfait aux propriétés suivantes :

  • La valeur d'un nœud dans un tas n'est toujours pas supérieure ou pas inférieure à la valeur de son nœud parent.
  • Un tas est toujours un arbre binaire complet.

II. Notes d'applicabilité

Un tas utilise la structure d'un arbre binaire complet pour maintenir un ensemble de données, puis effectue les opérations associées. La complexité temporelle d'une opération typique estO(1)~O(logn)Par ailleurs, les tas sont couramment utilisés pour allouer et libérer dynamiquement les objets utilisés par les programmes.

Pour un scénario d'utilisation de file de priorité, avec un tableau ordinaire ou un tableau ordonné, le pire cas estO(n^2)la structure de données de tas peut également améliorer l'efficacité des opérations d'enfilement et de défilement.

 EnfilerDéfiler
Tableau normalO(1)O(n)
Tableau ordonnéO(n)O(1)
TasO(logn)O(log)

III. Schéma de structure

Un tas binaire est un arbre binaire complet, et la valeur d'un nœud dans le tas n'est toujours pas supérieure à la valeur de son nœud parent. La profondeur de l'arbre binaire complet est k. À l'exception du k-ième niveau, le nombre de nœuds dans tous les autres niveaux (1 à k-1) atteint le maximum, et tous les nœuds du k-ième niveau sont continuellement concentrés du côté le plus à gauche.

Le tas dont le nœud racine est le plus grand est appelé tas max, comme le montre la figure ci-dessous :

Nous pouvons utiliser un tableau pour stocker le tas binaire ; les étiquettes à droite sont les indices du tableau.

En supposant que la position d'index de l'élément courant est i, nous pouvons en déduire la règle :

parent(i) = i/2(取整)
left child(i) = 2*i
right child(i) = 2*i +1

IV. Exemple de code Java

Téléchargement du paquet de code source :Télécharger

Code du fichier src/example/heap/MaxHeap.java :

package example.heap;

/**
* Définition du tas
 */

public class MaxHeap<T> {
    private T[] data;
    private int count;
    // Constructeur, construit un tas vide pouvant contenir capacity éléments
    public MaxHeap(int capacity){
        data = (T[])new Object[capacity+1];
        count = 0;
    }
    // Retourne le nombre d'éléments dans le tas
    public int size(){
        return count;
    }
    // Retourne un booléen indiquant si le tas est vide
    public boolean isEmpty(){
        return count == 0;
    }
    // Test MaxHeap
    public static void main(String[] args) {
        MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
        System.out.println(maxHeap.size());
    }
}
autres extensions