ヒープソート

Harshit Jindal 2023年10月12日
  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())

  • 配列 A 内に存在する要素で最大ヒープを構築します。
  • A の最後の要素から始まる各要素について、以下のようにします。
  • ルート要素 A[0] には最大の要素が含まれているので、この要素と入れ替える。
  • ヒープサイズを 1つ減らし、最後の要素を削除した最大ヒープを Heapify() します。

Heapify()

  • parent のインデックスを現在の要素のインデックスで初期化します。
  • leftChild2*i+1 とし、rightChild2*i+2 とします。
  • leftChild の要素が parent インデックスの値よりも大きい場合、parent インデックスを leftChild に設定します。
  • rightChild の要素が parent のインデックスの値よりも大きい場合、parent のインデックスを rightChild に設定します。
  • 最後の 2つのステップで parent インデックスの値が変更された場合は、親を現在の要素と入れ替え、再帰的に parent インデックスサブツリーを heapify します。そうでなければ、ヒーププロパティは既に満たされています。

ヒープソートの例

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

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

  • 最初の繰り返し
Swap(A[5],A[0]) 4 3 5 2 1 6
Heapify() 5 3 4 2 1 6
  • 2 回目の繰り返し
Swap(A[4],A[0]) 1 3 4 2 5 6
Heapify() 4 3 1 2 5 6
  • 3 回目の繰り返し
Swap(A[3],A[0]) 2 3 1 4 5 6
Heapify() 3 2 1 4 5 6
  • 4 回目の繰り返し
Swap(A[2],A[0]) 1 2 3 4 5 6
Heapify() 2 1 3 4 5 6
  • 5 回目の繰り返し
Swap(A[1],A[0]) 1 2 3 4 5 6
Heapify() 1 2 3 4 5 6
  • 6 回目の繰り返し
Swap(A[0],A[0]) 1 2 3 4 5 6
Heapify() 1 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) です。

著者: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

関連記事 - Sort Algorithm