So verwenden Sie den Heap-Sortieralgorithmus in C++

So verwenden Sie den Heap-Sortieralgorithmus in C++

Heap-Sortierung ist ein häufig verwendeter Sortieralgorithmus, der die Eigenschaften des Heaps zum Sortieren nutzt. Die Heap-Sortierung ist in zwei Schritte unterteilt: Heap-Erstellung und -Sortierung. In diesem Artikel erfahren Sie, wie Sie den Heap-Sortieralgorithmus mithilfe der C++-Sprache implementieren, und geben spezifische Codebeispiele.

1. Die Definition und Eigenschaften eines Heaps
   Ein Heap ist ein vollständiger Binärbaum, der in zwei Typen unterteilt werden kann: maximaler Heap und minimaler Heap. Der Wert jedes Knotens im Max-Heap ist größer oder gleich dem Wert seiner untergeordneten Knoten, und der Wert jedes Knotens im Min-Heap ist kleiner oder gleich dem Wert seiner untergeordneten Knoten. Im Heap-Sortieralgorithmus verwenden wir normalerweise den maximalen Heap.

Die Implementierung des Heaps kann durch ein Array dargestellt werden, und der Index des Arrays kann die Knotennummer im Heap darstellen. Für jeden Knoten i ist sein übergeordneter Knoten (i-1)/2, sein linker untergeordneter Knoten ist 2i+1 und sein rechter untergeordneter Knoten ist 2i+2.

2. Heap-Building-Algorithmus
   Der Heap-Building-Algorithmus ist der erste Schritt bei der Heap-Sortierung. Sein Zweck besteht darin, ein ungeordnetes Array zu einem Heap zusammenzustellen. Die Idee beim Aufbau eines Heaps besteht darin, beim letzten Nicht-Blattknoten des Arrays zu beginnen und an jedem Knoten eine Senkoperation durchzuführen, damit er die Eigenschaften eines Heaps erfüllt.

Das Folgende ist ein C++-Codebeispiel des Heap-Building-Algorithmus:

// 下沉操作，将指定节点下沉到合适的位置
void downAdjust(int arr[], int parent, int length) {
    int child = 2 * parent + 1; // 左子节点的下标
    int temp = arr[parent]; // 保存要下沉的节点的值
    
    while (child < length) {
        // 如果有右子节点，且右子节点的值大于左子节点的值，则选择右子节点
        if (child+1 < length && arr[child] < arr[child+1]) {
            child++;
        }
        
        // 如果父节点的值大于等于子节点的值，则下沉结束
        if (temp >= arr[child]) {
            break;
        }
        
        // 将子节点的值上移，代替父节点
        arr[parent] = arr[child];
        parent = child;
        child = 2 * parent + 1;
    }
    
    // 将要下沉的节点插入合适的位置
    arr[parent] = temp;
}

// 建堆算法，将无序数组构建成最大堆
void buildHeap(int arr[], int length) {
    // 从最后一个非叶子节点开始，依次进行下沉操作
    for (int i = (length-2) / 2; i >= 0; i--) {
        downAdjust(arr, i, length);
    }
}

3. Sortierungsalgorithmus
   Nachdem der Heap-Build abgeschlossen ist, können wir einen Sortiervorgang durchführen. Die Idee des Sortierens besteht darin, das oberste Element herauszunehmen des Heaps jedes Mal und tauschen Sie es mit dem Element am Ende des Heaps aus. Anschließend werden die restlichen Teile erneut versenkt.

Das Folgende ist ein C++-Codebeispiel des Heap-Sortieralgorithmus:

// 堆排序算法
void heapSort(int arr[], int length) {
    // 1. 构建最大堆
    buildHeap(arr, length);
    
    // 2. 排序
    for (int i = length - 1; i > 0; i--) {
        // 将堆顶元素与堆尾元素交换
        swap(arr[i], arr[0]);
        
        // 对剩下的部分重新进行下沉操作
        downAdjust(arr, 0, i);
    }
}

4. Beispiel und Test
   Das Folgende ist ein Beispiel und ein Test mit dem Heap-Sortieralgorithmus:

#include <iostream>

// 输出数组元素
void printArray(int arr[], int length) {
    for (int i = 0; i < length; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

// 主函数
int main() {
    int arr[] = {4, 1, 3, 9, 7};
    int length = sizeof(arr) / sizeof(int);
    
    std::cout << "排序前的数组：" << std::endl;
    printArray(arr, length);
    
    // 使用堆排序算法进行排序
    heapSort(arr, length);
    
    std::cout << "排序后的数组：" << std::endl;
    printArray(arr, length);
    
    return 0;
}

Das Ausgabeergebnis ist:

排序前的数组：
4 1 3 9 7 
排序后的数组：
1 3 4 7 9 

Mit Im obigen Beispiel und Test können wir sehen, dass der in C++ implementierte Heap-Sortieralgorithmus das Array korrekt sortieren kann.

Zusammenfassung:
Dieser Artikel stellt die Verwendung der C++-Sprache zum Implementieren des Heap-Sortieralgorithmus vor und enthält spezifische Codebeispiele. Der Kern des Heap-Sortieralgorithmus besteht in den beiden Schritten Heap-Erstellung und -Sortierung. Die Idee beim Erstellen eines Heaps besteht darin, den Senkvorgang vom letzten Nicht-Blattknoten aus zu starten das oberste Element des Heaps jedes Mal und tauschen Sie es mit dem Element am Ende des Heaps aus und versenken Sie die restlichen Teile erneut. Durch tatsächliche Tests können wir die Richtigkeit und Stabilität des Heap-Sortieralgorithmus überprüfen.

Das obige ist der detaillierte Inhalt vonSo verwenden Sie den Heap-Sortieralgorithmus in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!