Cara menggunakan algoritma isihan timbunan dalam C++

Cara menggunakan algoritma isihan timbunan dalam C++

Isihan timbunan ialah algoritma isihan yang biasa digunakan yang mengambil kesempatan daripada sifat timbunan untuk mengisih. Isih timbunan dibahagikan kepada dua langkah: membina timbunan dan menyusun. Dalam artikel ini, kita akan belajar cara melaksanakan algoritma isihan timbunan menggunakan bahasa C++ dan memberikan contoh kod khusus.

1. Takrifan dan sifat timbunan
   Timbunan ialah pokok binari lengkap, yang boleh dibahagikan kepada dua jenis: timbunan maksimum dan timbunan minimum. Nilai mana-mana nod dalam timbunan maks adalah lebih besar daripada atau sama dengan nilai nod anaknya, dan nilai mana-mana nod dalam timbunan min adalah kurang daripada atau sama dengan nilai nod anaknya. Dalam algoritma isihan timbunan, kami biasanya menggunakan timbunan maks.

Pelaksanaan timbunan boleh diwakili oleh tatasusunan, dan subskrip tatasusunan boleh mewakili nombor nod dalam timbunan. Untuk mana-mana nod i, nod induknya ialah (i-1)/2, nod anak kirinya ialah 2i+1, dan nod anak kanannya ialah 2i+2.

2. Algoritma binaan longgokan
   Algoritma binaan longgokan ialah langkah pertama dalam pengisihan longgokan. Idea membina timbunan adalah bermula dari nod bukan daun terakhir tatasusunan dan melakukan operasi tenggelam pada setiap nod supaya ia memenuhi sifat timbunan.

Berikut ialah contoh kod C++ bagi algoritma binaan timbunan:

// 下沉操作，将指定节点下沉到合适的位置
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. Algoritma pengisihan
   Selepas bangunan timbunan selesai, kita boleh melakukan operasi pengisihan Idea untuk menyusun elemen teratas timbunan setiap kali dan tukarkannya dengan elemen di hujung timbunan Kemudian tenggelamkan semula bahagian yang tinggal.

Berikut ialah contoh kod C++ bagi algoritma isihan timbunan:

// 堆排序算法
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. Contoh dan ujian
   Berikut ialah contoh dan ujian menggunakan algoritma isihan timbunan:

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

Hasil output ialah:

Wirreee contoh dan ujian di atas, Kita dapat melihat bahawa algoritma isihan timbunan yang dilaksanakan dalam C++ boleh mengisih tatasusunan dengan betul.

Ringkasan:

Artikel ini memperkenalkan cara menggunakan bahasa C++ untuk melaksanakan algoritma isihan timbunan dan memberikan contoh kod khusus. Inti algoritma pengisihan timbunan terletak pada dua langkah pembinaan timbunan dan pengisihan Idea untuk membina timbunan adalah untuk memulakan operasi tenggelam dari nod bukan daun yang terakhir elemen atas timbunan setiap kali dan tukarkannya dengan elemen di hujung timbunan , dan tenggelamkan semula bahagian yang tinggal. Melalui ujian sebenar, kami boleh mengesahkan ketepatan dan kestabilan algoritma isihan timbunan.

Atas ialah kandungan terperinci Cara menggunakan algoritma isihan timbunan dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!