Explication et implémentation de la version Java de l'algorithme de tri par tas

Le tas est une structure importante dans les structures de données. Si vous comprenez le concept et le fonctionnement du « tas », vous pouvez rapidement maîtriser le tri des tas.

Le concept de tas
Un tas est un arbre binaire complet spécial. Si la valeur de tous les nœuds d'un arbre binaire complet n'est pas inférieure à celle de ses nœuds enfants, on l'appelle un grand tas racine (ou grand tas supérieur) ; si la valeur de tous les nœuds n'est pas supérieure à ses nœuds enfants, on l'appelle ; un petit tas de racine (ou petit tas supérieur).
Dans le tableau (le nœud racine est stocké à l'indice 0), il est facile d'obtenir la formule suivante (ces deux formules sont très importantes) :
1 Le nœud avec l'indice i, les coordonnées du nœud parent. are ( i-1)/2;
2 Pour le nœud dont l'indice est i, les coordonnées du nœud enfant gauche sont 2*i 1 et le nœud enfant droit est 2*i 2.

Création et maintenance d'un tas
Le tas peut prendre en charge une variété d'opérations, mais maintenant nous ne nous préoccupons que de deux questions :
1 Étant donné un tableau non ordonné, comment le construire sous forme de tas ?
2. Après avoir supprimé l'élément supérieur du tas, comment ajuster le tableau dans un nouveau tas ?
Regardons d’abord la deuxième question. Supposons que nous ayons déjà un gros tas de racines prêt à fonctionner. Nous avons maintenant supprimé l'élément racine, mais n'avons déplacé aucun autre élément. Pensez à ce qui se passe : l'élément racine est vide, mais les autres éléments conservent la nature du tas. Nous pouvons déplacer le dernier élément (nom de code A) vers la position de l'élément racine. Si ce n’est pas un cas particulier, la nature du tas est détruite. Mais c’est uniquement parce que A est plus petit qu’un de ses enfants. Par conséquent, nous pouvons échanger les positions de A et de ce sous-élément. Si A est plus grand que tous ses sous-éléments, le tas est ajusté ; sinon, le processus ci-dessus est répété et l'élément A continue de « couler » dans la structure arborescente jusqu'à ce que la position appropriée soit atteinte, et le tableau retrouve son tas. propriétés. Le processus ci-dessus est généralement appelé « sélection » et la direction est évidemment descendante.
Il en va de même pour la suppression d'un élément, et il en va de même pour l'insertion d'un nouvel élément. La différence est que nous plaçons le nouvel élément à la fin, puis le comparons avec son nœud parent, c'est-à-dire un filtrage ascendant.
Alors, comment résoudre le premier problème ?
La plupart des livres sur la structure des données que j'ai lus filtrent à partir du premier nœud non-feuille jusqu'à ce que l'élément racine soit filtré. Cette méthode est appelée « méthode de filtrage » et nécessite un bouclage pour filtrer n/2 éléments.
Mais on peut aussi apprendre de l'idée de​​"faire quelque chose à partir de rien". Nous pouvons traiter le premier élément comme un tas et continuer à y ajouter de nouveaux éléments. Cette méthode est appelée « méthode d'insertion » et nécessite l'insertion de (n-1) éléments dans une boucle.
Étant donné que la méthode de filtrage et la méthode d'insertion sont différentes, les tas qu'elles créent pour les mêmes données sont généralement différents.

Après avoir une compréhension générale des tas, le tri des tas est une évidence.

Aperçu/Idées de l'algorithme
Nous avons besoin d'une séquence ascendante, que devons-nous faire ? Nous pouvons créer un min-heap, puis afficher l'élément racine à chaque fois. Cependant, cette méthode nécessite de l'espace supplémentaire (sinon elle entraînera le déplacement d'un grand nombre d'éléments et sa complexité montera jusqu'à O(n^2)). Que se passe-t-il si nous devons trier sur place (c'est-à-dire que la complexité de l'espace O(n) n'est pas autorisée) ?
Il existe un moyen. Nous pouvons construire un tas maximum, puis nous le produisons à l'envers, en produisant la valeur maximale à la dernière position et en produisant la deuxième plus grande valeur à la dernière position... Puisque la sortie de l'élément le plus grand à chaque fois libérera le premier espace. , nous pouvons simplement placer de tels éléments sans nécessiter d'espace supplémentaire. Jolie idée, n'est-ce pas ?

public class HeapSort {
  
  public static void main(String[] args) {
    int[] arr = { 50, 10, 90, 30, 70, 40, 80, 60, 20 };
    System.out.println("排序之前：");
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
  
    // 堆排序
    heapSort(arr);
  
    System.out.println();
    System.out.println("排序之后：");
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
  }
  
  /**
   * 堆排序
   */
  private static void heapSort(int[] arr) { 
    // 将待排序的序列构建成一个大顶堆
    for (int i = arr.length / 2; i >= 0; i--){ 
      heapAdjust(arr, i, arr.length); 
    }
      
    // 逐步将每个最大值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆
    for (int i = arr.length - 1; i > 0; i--) { 
      swap(arr, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
      heapAdjust(arr, 0, i); // 交换之后，需要重新检查堆是否符合大顶堆，不符合则要调整
    }
  }
  
  /**
   * 构建堆的过程
   * @param arr 需要排序的数组
   * @param i 需要构建堆的根节点的序号
   * @param n 数组的长度
   */
  private static void heapAdjust(int[] arr, int i, int n) {
    int child;
    int father; 
    for (father = arr[i]; leftChild(i) < n; i = child) {
      child = leftChild(i);
        
      // 如果左子树小于右子树，则需要比较右子树和父节点
      if (child != n - 1 && arr[child] < arr[child + 1]) {
        child++; // 序号增1，指向右子树
      }
        
      // 如果父节点小于孩子结点，则需要交换
      if (father < arr[child]) {
        arr[i] = arr[child];
      } else {
        break; // 大顶堆结构未被破坏，不需要调整
      }
    }
    arr[i] = father;
  }
  
  // 获取到左孩子结点
  private static int leftChild(int i) {
    return 2 * i + 1;
  }
    
  // 交换元素位置
  private static void swap(int[] arr, int index1, int index2) {
    int tmp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = tmp;
  }
}

Pour plus d'explications sur l'algorithme de tri par tas et des articles liés à l'implémentation de la version Java, veuillez faire attention au site Web PHP chinois !