Erläuterung und Java-Versionsimplementierung des Heap-Sortieralgorithmus

Heap ist eine wichtige Struktur in Datenstrukturen. Wenn Sie das Konzept und die Funktionsweise von „Heap“ verstehen, können Sie die Heap-Sortierung schnell beherrschen.

Das Konzept des Heaps
Ein Heap ist ein spezieller vollständiger Binärbaum. Wenn der Wert aller Knoten in einem vollständigen Binärbaum nicht kleiner ist als der seiner untergeordneten Knoten, wird er als Big-Root-Heap (oder Big-Top-Heap) bezeichnet. Wenn der Wert aller Knoten nicht größer ist als der seiner untergeordneten Knoten, wird er als Big-Root-Heap bezeichnet ein kleiner Root-Heap (oder kleiner Top-Heap).
Im Array (der Wurzelknoten wird bei Index 0 gespeichert) ist es einfach, die folgende Formel zu erhalten (diese beiden Formeln sind sehr wichtig):
1 Der Knoten mit dem Index i, die Koordinaten des übergeordneten Knotens sind ( i-1)/2; Für den Knoten, dessen Index i ist, sind die Koordinaten des linken untergeordneten Knotens 2*i+1 und die des rechten untergeordneten Knotens sind 2*i+2.

Heap kann eine Vielzahl von Vorgängen unterstützen, aber jetzt beschäftigen uns nur zwei Fragen:
1. Wie kann man ein ungeordnetes Array als Heap erstellen?
2. Wie passt man das Array nach dem Löschen des obersten Elements des Heaps in einen neuen Heap an?
Schauen wir uns zunächst die zweite Frage an. Gehen wir davon aus, dass wir bereits einen großen Wurzelhaufen bereit haben. Jetzt haben wir das Stammelement gelöscht, aber keine anderen Elemente verschoben. Denken Sie darüber nach, was passiert: Das Stammelement ist leer, aber die anderen Elemente behalten weiterhin die Heap-Natur bei. Wir können das letzte Element (Codename A) an die Position des Wurzelelements verschieben. Wenn es sich nicht um einen Sonderfall handelt, wird die Art des Heaps zerstört. Dies liegt aber nur daran, dass A kleiner ist als eines seiner Kinder. Daher können wir die Positionen von A und diesem Unterelement vertauschen. Wenn A größer als alle seine Unterelemente ist, wird der Heap angepasst. Andernfalls wird der obige Vorgang wiederholt und das A-Element „sinkt“ weiter in der Baumstruktur, bis die entsprechende Position erreicht ist und das Array seinen Heap zurückgewinnt Eigenschaften. Der obige Prozess wird im Allgemeinen als „Screening“ bezeichnet und die Richtung ist offensichtlich von oben nach unten.
Das Gleiche gilt für das Löschen eines Elements und das Gleiche gilt für das Einfügen eines neuen Elements. Der Unterschied besteht darin, dass wir das neue Element am Ende platzieren und es dann mit seinem übergeordneten Knoten vergleichen, also von unten nach oben filtern.
Wie lässt sich also das erste Problem lösen?
Viele der Datenstrukturbücher, die ich gelesen habe, filtern vom ersten Nicht-Blattknoten nach unten, bis das Wurzelelement gefiltert ist. Diese Methode wird „Screening-Methode“ genannt und erfordert eine Schleife zum Screening von n/2 Elementen.
Wir können aber auch von der Idee „aus dem Nichts etwas machen“ lernen. Wir können das erste Element als Heap behandeln und ihm immer wieder neue Elemente hinzufügen. Diese Methode wird „Einfügemethode“ genannt und erfordert das Einfügen von (n-1) Elementen in eine Schleife.
Da die Filtermethode und die Einfügemethode unterschiedlich sind, sind die Heaps, die sie für dieselben Daten erstellen, im Allgemeinen unterschiedlich.

Wir brauchen eine aufsteigende Reihenfolge, was sollen wir tun? Wir können einen Min-Heap erstellen und dann jedes Mal das Root-Element ausgeben. Diese Methode erfordert jedoch zusätzlichen Platz (andernfalls wird eine große Anzahl von Elementen verschoben und ihre Komplexität steigt auf O (n ^ 2)). Was ist, wenn wir an Ort und Stelle sortieren müssen (d. h. O(n)-Raumkomplexität ist nicht zulässig)?
Es gibt einen Weg. Wir können einen maximalen Heap erstellen und ihn dann rückwärts ausgeben, wobei wir an der letzten Position den Maximalwert und an der letzten Position den zweitgrößten Wert ausgeben ... Da jedes Mal das größte ausgegebene Element den ersten Platz freigibt Wir können solche Elemente einfach platzieren und benötigen keinen zusätzlichen Platz. Hübsche Idee, nicht wahr?

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;
  }
}