ヒープソート

1. ヒープソートアルゴリズム
2. ヒープソートの例
3. ヒープソートアルゴリズムの実装
4. ヒープソートアルゴリズムの複雑さ

ヒープソートは比較ベースのソートアルゴリズムです。その名前は、アルゴリズムで使用されるヒープデータ構造に由来しています。ヒープはバイナリツリーベースの特殊なデータ構造です。ヒープには以下の 2つの特性があります。

• 最後のレベルを除いてすべてのレベルが満たされた完全なバイナリツリーです。最後の 1つは部分的に満たされているかもしれませんが、すべてのノードは可能な限り左端にあります。
• すべての親ノードは、その 2つの子ノードよりも小さい/大きい。それらが小さい場合、ヒープは min-heap と呼ばれ、大きい場合は max-heap と呼ばれる。与えられたインデックス i に対して、親ノードは (i-1)/2 で与えられ、左の子ノードは (2*i+1) で与えられ、右の子ノードは (2*i+2) で与えられます。

ヒープソートの動作は選択ソートとよく似ています。ヒープソートは配列の中から最大の要素を max-heap を用いて選択し、それを配列の末尾の位置に配置します。ヒープを構築するために heapify() という手続きを利用します。

ヒープソートアルゴリズム

ここでは、n 要素を含むソートされていない配列 A[] があるとします。

HeapSort())

Heapify()

ヒープソートの例

配列 （5、3、4、2、1、6）があるとします。ヒープソートアルゴリズムを使用してソートします。

ヒープを構築すると、配列は次のようになります：(6 3 5 2 1 4)。

• 最初の繰り返し

• 2 回目の繰り返し

• 3 回目の繰り返し

• 4 回目の繰り返し

• 5 回目の繰り返し

• 6 回目の繰り返し

ソートされた配列は次のようになります：(1,2,3,4,5,6)。

ヒープソートアルゴリズムの実装

#include <bits/stdc++.h>
using namespace std;

void heapify(int arr[], int n, int i) {
  int parent = i;
  int leftChild = 2 * i + 1;
  int rightChild = 2 * i + 2;

  if (leftChild < n && arr[leftChild] > arr[parent]) parent = leftChild;

  if (rightChild < n && arr[rightChild] > arr[parent]) parent = rightChild;

  if (parent != i) {
    swap(arr[i], arr[parent]);
    heapify(arr, n, parent);
  }
}

void heapSort(int arr[], int n) {
  for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);

  for (int i = n - 1; i >= 0; i--) {
    swap(arr[0], arr[i]);
    heapify(arr, i, 0);
  }
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  heapSort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

ヒープソートアルゴリズムの複雑さ

時間複雑度

• 平均のケース

n 個の要素を持つ完全な二分木の高さは最大 logn です。したがって、heapify() 関数は要素がルートからリーフに移動するときに最大で logn の比較を行うことができます。ビルドヒープ関数は n/2 個の要素に対して呼び出されるので、最初の段階の総時間の複雑さは n/2*logn または T(n) = nlogn となります。

HeapSort() は要素ごとに logn のワーストタイムをとり、n 個の要素があるため、その時間的複雑さも nlogn となります。ヒープの構築とヒープソートの時間的複雑さを足し合わせた結果が nlogn です。したがって、時間的複雑度の合計は [Big Theta]のオーダーである: O(nlogn) となります。

• 最悪のケース

最悪の場合の時間的複雑さは [Big O]: O(nlogn) です。

• 最良のケース

最良の時間複雑度は [Big Omega]: O(nlogn) です。これは最悪の時間複雑度と同じです。

空間計算量

ヒープソートアルゴリズムの空間複雑度は、一時変数以外に余分なメモリを必要としないため、O(1) です。