11.7 ヒープソート¶

Tip

本節を読む前に、「ヒープ」の章を学習済みであることを確認してください。

ヒープソート（heap sort）は、ヒープデータ構造に基づいて実装される効率的なソートアルゴリズムです。すでに学んだ「ヒープ構築操作」と「要素の取り出し操作」を利用してヒープソートを実現できます。

配列を入力して最小ヒープを構築すると、このとき最小要素はヒープの頂点にあります。
取り出し操作を繰り返し実行し、取り出された要素を順に記録すれば、昇順に並んだ列が得られます。

以上の方法でも実行できますが、取り出した要素を保存するために追加の配列が必要となり、空間をやや無駄にします。実際には、通常はより洗練された実装方法を用います。

11.7.1 アルゴリズムの流れ¶

配列の長さを \(n\) とすると、ヒープソートの流れは次図のとおりです。

配列を入力して最大ヒープを構築します。完了後、最大要素はヒープの頂点にあります。
ヒープ頂点の要素（最初の要素）とヒープ末尾の要素（最後の要素）を交換します。交換後、ヒープの長さは \(1\) 減少し、整列済み要素数は \(1\) 増加します。
ヒープ頂点の要素から始めて、上から下へヒープ化操作（sift down）を実行します。ヒープ化が完了すると、ヒープの性質が回復します。
第 2. ステップと第 3. ステップを繰り返し実行します。これを \(n - 1\) 回繰り返すと、配列の整列が完了します。

Tip

実際には、要素の取り出し操作にも第 2. ステップと第 3. ステップが含まれており、要素を取り出す処理が 1 つ加わるだけです。

図 11-12 ヒープソートの手順

コード実装では、「ヒープ」の章と同じ上から下へのヒープ化 sift_down() 関数を使用します。注意すべき点として、ヒープの長さは最大要素を取り出すたびに短くなるため、sift_down() 関数に長さパラメータ \(n\) を追加し、ヒープの現在の有効な長さを指定する必要があります。コードは以下のとおりです。

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

heap_sort.py

def sift_down(nums: list[int], n: int, i: int):
    """ヒープの長さは n。ノード i から下方向にヒープ化"""
    while True:
        # ノード i, l, r のうち値が最大のノードを ma とする
        l = 2 * i + 1
        r = 2 * i + 2
        ma = i
        if l < n and nums[l] > nums[ma]:
            ma = l
        if r < n and nums[r] > nums[ma]:
            ma = r
        # ノード i が最大、またはインデックス l, r が範囲外なら、ヒープ化は不要なので抜ける
        if ma == i:
            break
        # 2 つのノードを交換
        nums[i], nums[ma] = nums[ma], nums[i]
        # ループで上から下へヒープ化
        i = ma

def heap_sort(nums: list[int]):
    """ヒープソート"""
    # ヒープ構築：葉ノード以外のすべてのノードをヒープ化する
    for i in range(len(nums) // 2 - 1, -1, -1):
        sift_down(nums, len(nums), i)
    # ヒープから最大要素を取り出し、n-1 回繰り返す
    for i in range(len(nums) - 1, 0, -1):
        # 根ノードと最も右の葉ノードを交換（先頭要素と末尾要素を交換）
        nums[0], nums[i] = nums[i], nums[0]
        # 根ノードを起点に、上から下へヒープ化
        sift_down(nums, i, 0)

heap_sort.cpp

/* ヒープの長さは n。ノード i から下方向にヒープ化 */
void siftDown(vector<int> &nums, int n, int i) {
    while (true) {
        // ノード i, l, r のうち値が最大のノードを ma とする
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma])
            ma = l;
        if (r < n && nums[r] > nums[ma])
            ma = r;
        // ノード i が最大、またはインデックス l, r が範囲外なら、ヒープ化は不要なので抜ける
        if (ma == i) {
            break;
        }
        // 2 つのノードを交換
        swap(nums[i], nums[ma]);
        // ループで上から下へヒープ化
        i = ma;
    }
}

/* ヒープソート */
void heapSort(vector<int> &nums) {
    // ヒープ構築：葉ノード以外のすべてのノードをヒープ化する
    for (int i = nums.size() / 2 - 1; i >= 0; --i) {
        siftDown(nums, nums.size(), i);
    }
    // ヒープから最大要素を取り出し、n-1 回繰り返す
    for (int i = nums.size() - 1; i > 0; --i) {
        // 根ノードと最も右の葉ノードを交換（先頭要素と末尾要素を交換）
        swap(nums[0], nums[i]);
        // 根ノードを起点に、上から下へヒープ化
        siftDown(nums, i, 0);
    }
}

heap_sort.java

/* ヒープの長さは n。ノード i から下方向にヒープ化 */
void siftDown(int[] nums, int n, int i) {
    while (true) {
        // ノード i, l, r のうち値が最大のノードを ma とする
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma])
            ma = l;
        if (r < n && nums[r] > nums[ma])
            ma = r;
        // ノード i が最大、またはインデックス l, r が範囲外なら、ヒープ化は不要なので抜ける
        if (ma == i)
            break;
        // 2 つのノードを交換
        int temp = nums[i];
        nums[i] = nums[ma];
        nums[ma] = temp;
        // ループで上から下へヒープ化
        i = ma;
    }
}

/* ヒープソート */
void heapSort(int[] nums) {
    // ヒープ構築：葉ノード以外のすべてのノードをヒープ化する
    for (int i = nums.length / 2 - 1; i >= 0; i--) {
        siftDown(nums, nums.length, i);
    }
    // ヒープから最大要素を取り出し、n-1 回繰り返す
    for (int i = nums.length - 1; i > 0; i--) {
        // 根ノードと最も右の葉ノードを交換（先頭要素と末尾要素を交換）
        int tmp = nums[0];
        nums[0] = nums[i];
        nums[i] = tmp;
        // 根ノードを起点に、上から下へヒープ化
        siftDown(nums, i, 0);
    }
}

heap_sort.cs

/* ヒープの長さは n。ノード i から下方向にヒープ化 */
void SiftDown(int[] nums, int n, int i) {
    while (true) {
        // ノード i, l, r のうち値が最大のノードを ma とする
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma])
            ma = l;
        if (r < n && nums[r] > nums[ma])
            ma = r;
        // ノード i が最大、またはインデックス l, r が範囲外なら、ヒープ化は不要なので抜ける
        if (ma == i)
            break;
        // 2 つのノードを交換
        (nums[ma], nums[i]) = (nums[i], nums[ma]);
        // ループで上から下へヒープ化
        i = ma;
    }
}

/* ヒープソート */
void HeapSort(int[] nums) {
    // ヒープ構築：葉ノード以外のすべてのノードをヒープ化する
    for (int i = nums.Length / 2 - 1; i >= 0; i--) {
        SiftDown(nums, nums.Length, i);
    }
    // ヒープから最大要素を取り出し、n-1 回繰り返す
    for (int i = nums.Length - 1; i > 0; i--) {
        // 根ノードと最も右の葉ノードを交換（先頭要素と末尾要素を交換）
        (nums[i], nums[0]) = (nums[0], nums[i]);
        // 根ノードを起点に、上から下へヒープ化
        SiftDown(nums, i, 0);
    }
}

heap_sort.go

/* ヒープの長さは n。ノード i から下方向にヒープ化 */
func siftDown(nums *[]int, n, i int) {
    for true {
        // ノード i, l, r のうち値が最大のノードを ma とする
        l := 2*i + 1
        r := 2*i + 2
        ma := i
        if l < n && (*nums)[l] > (*nums)[ma] {
            ma = l
        }
        if r < n && (*nums)[r] > (*nums)[ma] {
            ma = r
        }
        // ノード i が最大、またはインデックス l, r が範囲外なら、ヒープ化は不要なので抜ける
        if ma == i {
            break
        }
        // 2 つのノードを交換
        (*nums)[i], (*nums)[ma] = (*nums)[ma], (*nums)[i]
        // ループで上から下へヒープ化
        i = ma
    }
}

/* ヒープソート */
func heapSort(nums *[]int) {
    // ヒープ構築：葉ノード以外のすべてのノードをヒープ化する
    for i := len(*nums)/2 - 1; i >= 0; i-- {
        siftDown(nums, len(*nums), i)
    }
    // ヒープから最大要素を取り出し、n-1 回繰り返す
    for i := len(*nums) - 1; i > 0; i-- {
        // 根ノードと最も右の葉ノードを交換（先頭要素と末尾要素を交換）
        (*nums)[0], (*nums)[i] = (*nums)[i], (*nums)[0]
        // 根ノードを起点に、上から下へヒープ化
        siftDown(nums, i, 0)
    }
}

heap_sort.swift

/* ヒープの長さは n。ノード i から下方向にヒープ化 */
func siftDown(nums: inout [Int], n: Int, i: Int) {
    var i = i
    while true {
        // ノード i, l, r のうち値が最大のノードを ma とする
        let l = 2 * i + 1
        let r = 2 * i + 2
        var ma = i
        if l < n, nums[l] > nums[ma] {
            ma = l
        }
        if r < n, nums[r] > nums[ma] {
            ma = r
        }
        // ノード i が最大、またはインデックス l, r が範囲外なら、ヒープ化は不要なので抜ける
        if ma == i {
            break
        }
        // 2 つのノードを交換
        nums.swapAt(i, ma)
        // ループで上から下へヒープ化
        i = ma
    }
}

/* ヒープソート */
func heapSort(nums: inout [Int]) {
    // ヒープ構築：葉ノード以外のすべてのノードをヒープ化する
    for i in stride(from: nums.count / 2 - 1, through: 0, by: -1) {
        siftDown(nums: &nums, n: nums.count, i: i)
    }
    // ヒープから最大要素を取り出し、n-1 回繰り返す
    for i in nums.indices.dropFirst().reversed() {
        // 根ノードと最も右の葉ノードを交換（先頭要素と末尾要素を交換）
        nums.swapAt(0, i)
        // 根ノードを起点に、上から下へヒープ化
        siftDown(nums: &nums, n: i, i: 0)
    }
}

heap_sort.js

/* ヒープの長さは n。ノード i から下方向にヒープ化 */
function siftDown(nums, n, i) {
    while (true) {
        // ノード i, l, r のうち値が最大のノードを ma とする
        let l = 2 * i + 1;
        let r = 2 * i + 2;
        let ma = i;
        if (l < n && nums[l] > nums[ma]) {
            ma = l;
        }
        if (r < n && nums[r] > nums[ma]) {
            ma = r;
        }
        // ノード i が最大、またはインデックス l, r が範囲外なら、ヒープ化は不要なので抜ける
        if (ma === i) {
            break;
        }
        // 2 つのノードを交換
        [nums[i], nums[ma]] = [nums[ma], nums[i]];
        // ループで上から下へヒープ化
        i = ma;
    }
}

/* ヒープソート */
function heapSort(nums) {
    // ヒープ構築：葉ノード以外のすべてのノードをヒープ化する
    for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
        siftDown(nums, nums.length, i);
    }
    // ヒープから最大要素を取り出し、n-1 回繰り返す
    for (let i = nums.length - 1; i > 0; i--) {
        // 根ノードと最も右の葉ノードを交換（先頭要素と末尾要素を交換）
        [nums[0], nums[i]] = [nums[i], nums[0]];
        // 根ノードを起点に、上から下へヒープ化
        siftDown(nums, i, 0);
    }
}

heap_sort.ts

/* ヒープの長さは n。ノード i から下方向にヒープ化 */
function siftDown(nums: number[], n: number, i: number): void {
    while (true) {
        // ノード i, l, r のうち値が最大のノードを ma とする
        let l = 2 * i + 1;
        let r = 2 * i + 2;
        let ma = i;
        if (l < n && nums[l] > nums[ma]) {
            ma = l;
        }
        if (r < n && nums[r] > nums[ma]) {
            ma = r;
        }
        // ノード i が最大、またはインデックス l, r が範囲外なら、ヒープ化は不要なので抜ける
        if (ma === i) {
            break;
        }
        // 2 つのノードを交換
        [nums[i], nums[ma]] = [nums[ma], nums[i]];
        // ループで上から下へヒープ化
        i = ma;
    }
}

/* ヒープソート */
function heapSort(nums: number[]): void {
    // ヒープ構築：葉ノード以外のすべてのノードをヒープ化する
    for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
        siftDown(nums, nums.length, i);
    }
    // ヒープから最大要素を取り出し、n-1 回繰り返す
    for (let i = nums.length - 1; i > 0; i--) {
        // 根ノードと最も右の葉ノードを交換（先頭要素と末尾要素を交換）
        [nums[0], nums[i]] = [nums[i], nums[0]];
        // 根ノードを起点に、上から下へヒープ化
        siftDown(nums, i, 0);
    }
}

heap_sort.dart

/* ヒープの長さは n。ノード i から下方向にヒープ化 */
void siftDown(List<int> nums, int n, int i) {
  while (true) {
    // ノード i, l, r のうち値が最大のノードを ma とする
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int ma = i;
    if (l < n && nums[l] > nums[ma]) ma = l;
    if (r < n && nums[r] > nums[ma]) ma = r;
    // ノード i が最大、またはインデックス l, r が範囲外なら、ヒープ化は不要なので抜ける
    if (ma == i) break;
    // 2 つのノードを交換
    int temp = nums[i];
    nums[i] = nums[ma];
    nums[ma] = temp;
    // ループで上から下へヒープ化
    i = ma;
  }
}

/* ヒープソート */
void heapSort(List<int> nums) {
  // ヒープ構築：葉ノード以外のすべてのノードをヒープ化する
  for (int i = nums.length ~/ 2 - 1; i >= 0; i--) {
    siftDown(nums, nums.length, i);
  }
  // ヒープから最大要素を取り出し、n-1 回繰り返す
  for (int i = nums.length - 1; i > 0; i--) {
    // 根ノードと最も右の葉ノードを交換（先頭要素と末尾要素を交換）
    int tmp = nums[0];
    nums[0] = nums[i];
    nums[i] = tmp;
    // 根ノードを起点に、上から下へヒープ化
    siftDown(nums, i, 0);
  }
}

heap_sort.rs

/* ヒープの長さは n。ノード i から下方向にヒープ化 */
fn sift_down(nums: &mut [i32], n: usize, mut i: usize) {
    loop {
        // ノード i, l, r のうち値が最大のノードを ma とする
        let l = 2 * i + 1;
        let r = 2 * i + 2;
        let mut ma = i;
        if l < n && nums[l] > nums[ma] {
            ma = l;
        }
        if r < n && nums[r] > nums[ma] {
            ma = r;
        }
        // ノード i が最大、またはインデックス l, r が範囲外なら、ヒープ化は不要なので抜ける
        if ma == i {
            break;
        }
        // 2 つのノードを交換
        nums.swap(i, ma);
        // ループで上から下へヒープ化
        i = ma;
    }
}

/* ヒープソート */
fn heap_sort(nums: &mut [i32]) {
    // ヒープ構築：葉ノード以外のすべてのノードをヒープ化する
    for i in (0..nums.len() / 2).rev() {
        sift_down(nums, nums.len(), i);
    }
    // ヒープから最大要素を取り出し、n-1 回繰り返す
    for i in (1..nums.len()).rev() {
        // 根ノードと最も右の葉ノードを交換（先頭要素と末尾要素を交換）
        nums.swap(0, i);
        // 根ノードを起点に、上から下へヒープ化
        sift_down(nums, i, 0);
    }
}

heap_sort.c

/* ヒープの長さは n。ノード i から下方向にヒープ化 */
void siftDown(int nums[], int n, int i) {
    while (1) {
        // ノード i, l, r のうち値が最大のノードを ma とする
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma])
            ma = l;
        if (r < n && nums[r] > nums[ma])
            ma = r;
        // ノード i が最大、またはインデックス l, r が範囲外なら、ヒープ化は不要なので抜ける
        if (ma == i) {
            break;
        }
        // 2 つのノードを交換
        int temp = nums[i];
        nums[i] = nums[ma];
        nums[ma] = temp;
        // ループで上から下へヒープ化
        i = ma;
    }
}

/* ヒープソート */
void heapSort(int nums[], int n) {
    // ヒープ構築：葉ノード以外のすべてのノードをヒープ化する
    for (int i = n / 2 - 1; i >= 0; --i) {
        siftDown(nums, n, i);
    }
    // ヒープから最大要素を取り出し、n-1 回繰り返す
    for (int i = n - 1; i > 0; --i) {
        // 根ノードと最も右の葉ノードを交換（先頭要素と末尾要素を交換）
        int tmp = nums[0];
        nums[0] = nums[i];
        nums[i] = tmp;
        // 根ノードを起点に、上から下へヒープ化
        siftDown(nums, i, 0);
    }
}

heap_sort.kt

/* ヒープの長さは n。ノード i から下方向にヒープ化 */
fun siftDown(nums: IntArray, n: Int, li: Int) {
    var i = li
    while (true) {
        // ノード i, l, r のうち値が最大のノードを ma とする
        val l = 2 * i + 1
        val r = 2 * i + 2
        var ma = i
        if (l < n && nums[l] > nums[ma]) 
            ma = l
        if (r < n && nums[r] > nums[ma]) 
            ma = r
        // ノード i が最大、またはインデックス l, r が範囲外なら、ヒープ化は不要なので抜ける
        if (ma == i) 
            break
        // 2 つのノードを交換
        val temp = nums[i]
        nums[i] = nums[ma]
        nums[ma] = temp
        // ループで上から下へヒープ化
        i = ma
    }
}

/* ヒープソート */
fun heapSort(nums: IntArray) {
    // ヒープ構築：葉ノード以外のすべてのノードをヒープ化する
    for (i in nums.size / 2 - 1 downTo 0) {
        siftDown(nums, nums.size, i)
    }
    // ヒープから最大要素を取り出し、n-1 回繰り返す
    for (i in nums.size - 1 downTo 1) {
        // 根ノードと最も右の葉ノードを交換（先頭要素と末尾要素を交換）
        val temp = nums[0]
        nums[0] = nums[i]
        nums[i] = temp
        // 根ノードを起点に、上から下へヒープ化
        siftDown(nums, i, 0)
    }
}

heap_sort.rb

### ヒープ長 n で、ノード i から上から下へヒープ化 ###
def sift_down(nums, n, i)
  while true
    # ノード i, l, r のうち値が最大のノードを ma とする
    l = 2 * i + 1
    r = 2 * i + 2
    ma = i
    ma = l if l < n && nums[l] > nums[ma]
    ma = r if r < n && nums[r] > nums[ma]
    # ノード i が最大、またはインデックス l, r が範囲外なら、ヒープ化は不要なので抜ける
    break if ma == i
    # 2 つのノードを交換
    nums[i], nums[ma] = nums[ma], nums[i]
    # ループで上から下へヒープ化
    i = ma
  end
end

### ヒープソート ###
def heap_sort(nums)
  # ヒープ構築：葉ノード以外のすべてのノードをヒープ化する
  (nums.length / 2 - 1).downto(0) do |i|
    sift_down(nums, nums.length, i)
  end
  # ヒープから最大要素を取り出し、n-1 回繰り返す
  (nums.length - 1).downto(1) do |i|
    # 根ノードと最も右の葉ノードを交換（先頭要素と末尾要素を交換）
    nums[0], nums[i] = nums[i], nums[0]
    # 根ノードを起点に、上から下へヒープ化
    sift_down(nums, i, 0)
  end
end

コードの可視化

全画面で見る >

11.7.2 アルゴリズムの特性¶

時間計算量は \(O(n \log n)\)、非適応ソート：ヒープ構築操作には \(O(n)\) の時間がかかります。ヒープから最大要素を取り出す時間計算量は \(O(\log n)\) であり、これを合計 \(n - 1\) 回繰り返します。
空間計算量は \(O(1)\)、インプレースソート：いくつかのポインタ変数が使う空間は \(O(1)\) です。要素の交換とヒープ化操作はいずれも元の配列上で行われます。
非安定ソート：ヒープ頂点の要素とヒープ末尾の要素を交換する際、等しい要素どうしの相対位置が変化する可能性があります。

11.7 ヒープソート¶

11.7.1 アルゴリズムの流れ¶

11.7.2 アルゴリズムの特性¶

ご意見、ご質問、ご提案があればぜひコメントしてください