C++ でヒープ ソート アルゴリズムを使用する方法

C でヒープ ソート アルゴリズムを使用する方法

ヒープ ソートは、並べ替えにヒープのプロパティを使用する、一般的に使用される並べ替えアルゴリズムです。ヒープ ソートは、ヒープの構築とソートの 2 つのステップに分かれています。この記事では、C 言語を使用してヒープ ソート アルゴリズムを実装する方法を学び、具体的なコード例を示します。

1. ヒープの定義とプロパティ
   ヒープは完全なバイナリ ツリーであり、最大ヒープと最小ヒープの 2 つのタイプに分類できます。最大ヒープ内の任意のノードの値はその子ノードの値以上であり、最小ヒープ内の任意のノードの値はその子ノードの値以下です。ヒープソートアルゴリズムでは、通常、最大ヒープを使用します。

ヒープの実装は配列で表すことができ、配列の添字はヒープ内のノード番号を表すことができます。任意のノード i について、その親ノードは (i-1)/2、その左側の子ノードは 2i 1、右側の子ノードは 2i 2 です。

2. ヒープ構築アルゴリズム
   ヒープ構築アルゴリズムは、ヒープ ソートの最初のステップであり、その目的は、順序なし配列をヒープに構築することです。ヒープを構築するという考え方は、配列の最後の非リーフ ノードから開始して、ヒープのプロパティを満たすように各ノードでシンク操作を実行することです。

次に、ヒープ構築アルゴリズムの C コード例を示します。

// 下沉操作，将指定节点下沉到合适的位置
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. ソート アルゴリズム
   ヒープ構築が完了したら、ソート操作を実行できます。ソートの考え方は、ヒープの先頭の要素を取り出し、それをヒープの末尾の要素と交換し、残りの部分に対して再度シンク操作を実行することです。

次は、ヒープ ソート アルゴリズムの C コード例です。

// 堆排序算法
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. 例とテスト
   次は、ヒープ ソート アルゴリズムを使用した例とテストです。 :

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

出力結果は次のとおりです:

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

上記の例とテストを通じて、C 言語で実装されたヒープ ソート アルゴリズムが配列を正しくソートできることがわかります。

概要:
この記事では、C 言語を使用してヒープ ソート アルゴリズムを実装する方法を紹介し、具体的なコード例を示します。ヒープ ソート アルゴリズムの核心は、ヒープの構築とソートの 2 つのステップにあります。ヒープの構築のアイデアは、最後の非リーフ ノードからシンク操作を開始することです。ソートのアイデアは、ヒープの構築とソートの 2 つのステップです。毎回ヒープの先頭の要素を取得してヒープの末尾の要素と交換し、残りの部分を再シンクします。実際のテストを通じて、ヒープソートアルゴリズムの正確性と安定性を検証できます。

以上がC++ でヒープ ソート アルゴリズムを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。