【C#】上位 k 件を得る (1) - ヒープソート

一記事にまとめるとボリューミー過ぎるので分割。
なお、この記事には上位 k 件を得る話までいかず、ヒープソートの話まで。

ヒープ構造は数々の場所で解説されてるのであえてその解説はせず、C++ のmake_heap、pop_heap、sort_heapの C# 実装といった感じの内容になる。

まずは指定の範囲をヒープ化するmake_heap。
参考：make_heap - cpprefjp C++日本語リファレンス

public static void MakeHeap<T>(scoped Span<T> span) => MakeHeap(span, Comparer<T>.Default);
public static void MakeHeap<T>(scoped Span<T> span, IComparer<T> comparer)
{
    int len = span.Length;
    for (int top = len / 2 - 1; top >= 0; --top)
    {
        T v = span[top];
        int p = top;
        for (int c = p * 2 + 1; c < len; c = p * 2 + 1)
        {
            if (c + 1 < len && (comparer.Compare(span[c], span[c + 1])) < 1)
                ++c;
            if ((comparer.Compare(v, span[c]) < 1) is false)
                break;

            span[p] = span[c];
            p = c;
        }

        span[p] = v;
    }
}

var array = Enumerable.Range(0, 16).ToArray();
var rand = new Random(2023);
var span = array.AsSpan();
SortUtil.Shuffle(span, rand); // Shuffle というメソッドがあるものとする

Console.WriteLine(span.ToListString()); // ToListString という拡張メソッドがあるものとする
SortUtil.MakeHeap(span);
Console.WriteLine(span.ToListString());

// [8, 0, 7, 13, 5, 10, 1, 2, 15, 3, 12, 14, 4, 11, 6, 9]
// [15, 13, 14, 9, 12, 10, 11, 8, 0, 3, 5, 7, 4, 1, 6, 2]

一段目が元で、二段目がmake_heap後。
配列内でヒープ構造がつくられている。先頭が最大なのが特徴的。

次にpop_heap。
これは、ヒープ化された範囲の先頭と末尾を入れ替え、末尾を除いた範囲を再びヒープ化する。
参考：pop_heap - cpprefjp C++日本語リファレンス

public static void PopHeap<T>(scoped Span<T> heap) => PopHeap(heap, Comparer<T>.Default);
public static void PopHeap<T>(scoped Span<T> heap, IComparer<T> comparer)
{
    int len = heap.Length - 1;
    if (len <= 0) return;

    T v = heap[len];
    heap[len] = heap[0];
    int p = 0;
    for (int c = 1; c < len; c = p * 2 + 1)
    {
        if (c + 1 < len && comparer.Compare(heap[c], heap[c + 1]) < 1)
            ++c;
        if ((comparer.Compare(v, heap[c]) < 1) is false)
            break;
        heap[p] = heap[c];
        p = c;
    }
    heap[p] = v;
}

var span2 = span.ToArray().AsSpan();
SortUtil.PopHeap(span2);
Console.WriteLine(span2.ToListString());
// [14, 13, 11, 9, 12, 10, 6, 8, 0, 3, 5, 7, 4, 1, 2, 15]

先頭の 15 が末尾にポップされている。
それ以外の範囲が再びヒープ化されて、最大の14が先頭になっている。

そしてsort_heap。
これは、ヒープ化された範囲を昇順にソートする。

public static void SortHeap<T>(scoped Span<T> heap) => SortHeap(heap, Comparer<T>.Default);
public static void SortHeap<T>(scoped Span<T> heap, IComparer<T> comparer)
{
    int last = heap.Length;
    while(last > 0)
    {
        heap = heap[..last--];
        PopHeap(heap, comparer);
    }
}

SortUtil.SortHeap(span);
Console.WriteLine(span.ToListString());
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

pop_heapが最大要素を末尾にポップし残りの範囲をヒープ化するわけだから、ポップした範囲を除いて次々とpop_heapしていくと全体がソート済みになる。
ヒープソート。

ソートとして見た場合、純粋なヒープソートはあまり強みを持っているとは必ずしも言えない。

けれども、上位 k 件を得るという場合にヒープ構造を利用することができる。
(2) へ続く。
aneuf.hatenablog.com

てくメモ

trivial な notes

【C#】上位 k 件を得る (1) - ヒープソート