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

拡張メソッドでIListをソートする

C#拡張メソッドによるヒープソートの実装

　ここまでに説明したアルゴリズムをC#の拡張メソッドで実装しました。C++標準ライブラリにheapに関する基本処理が実装されているので、ここではC++標準ライブラリのフリーの実装: STLport にあるheap実装を忠実にC#に移植しました。

Heap.cs

using System.Collections.Generic;
using System;

namespace Epsteme.Collections.Generic.Extensions {

  public static class IListExtensions {

    private static void __push_heap<T>(this IList<T> self, int first, int holeindex, int topindex, T val, Comparison<T> comp) {
      int parent = (holeindex - 1) / 2;
      while (holeindex > topindex && comp(self[first + parent], val) < 0) {
        self[first + holeindex] = self[first + parent]; 
        holeindex = parent;
        parent = (holeindex - 1) / 2;
      }
      self[first + holeindex] = val;
    }

    private static void __push_heap_aux<T>(this IList<T> self, int first, int last, Comparison<T> comp) {
      self.__push_heap(first, last - first - 1, 0, self[last - 1], comp);
    }

    private static void __adjust_heap<T>(this IList<T> self, int first, int holeindex, int len, T val, Comparison<T> comp) {
      int topindex = holeindex;
      int secondChild = 2 * holeindex + 2;
      while (secondChild < len) {
        if (comp(self[first + secondChild], self[first + secondChild - 1]) < 0) {
          --secondChild;
        }
        self[first + holeindex] = self[first + secondChild];
        holeindex = secondChild;
        secondChild = 2 * (secondChild + 1);
      }
      if (secondChild == len) {
        self[first + holeindex] = self[first + secondChild - 1];
        holeindex = secondChild - 1;
      }
      self.__push_heap(first, holeindex, topindex,val, comp);
    }

    private static void __pop_heap<T>(this IList<T> self, int first, int last, int result, T val, Comparison<T> comp) {
      self[result] = self[first];
      self.__adjust_heap(first, 0, last-first,val,comp);
    }

    private static void __pop_heap_aux<T>(this IList<T> self, int first, int last, Comparison<T> comp) {
      self.__pop_heap(first, last - 1, last - 1, self[last - 1], comp);
    }

    private static void __make_heap<T>(this IList<T> self, int first, int last, Comparison<T> comp) {
      if (last - first < 2) return;
      int len = last - first;
      int parent = (len - 2) / 2;
      for ( ; ; ) {
        self.__adjust_heap(first, parent, len, self[first + parent], comp);
        if (parent == 0) return;
        --parent;
      }
    }

    public static Comparison<T> DefaultComparison<T>(this IList<T> self) where T : IComparable<T> {
      return (T x, T y) => x.CompareTo(y);
    }

    public static void PushHeap<T>(this IList<T> self, int first, int last, Comparison<T> comp) {
      self.__push_heap_aux(first, last, comp);
    }

    public static void PushHeap<T>(this IList<T> self, Comparison<T> comp) {
      self.__push_heap_aux(0, self.Count, comp);
    }

    public static void PopHeap<T>(this IList<T> self, int first, int last, Comparison<T> comp) {
      self.__pop_heap_aux(first, last, comp);
    }

    public static void PopHeap<T>(this IList<T> self, Comparison<T> comp) {
      self.__pop_heap_aux(0, self.Count, comp);
    }

    public static void MakeHeap<T>(this IList<T> self, int first, int last, Comparison<T> comp) {
      self.__make_heap(first, last, comp);
    }

    public static void MakeHeap<T>(this IList<T> self, Comparison<T> comp) {
      self.__make_heap(0, self.Count, comp);
    }

    public static void SortHeap<T>(this IList<T> self, int first, int last, Comparison<T> comp) {
      while (last - first > 1)
        self.PopHeap(first, last--, comp);
    }

    public static void SortHeap<T>(this IList<T> self, Comparison<T> comp) {
      self.SortHeap(0, self.Count, comp);
    }

  }
}

　実装されているメソッドを簡単に説明します。

　各メソッドに与えられるdelegate int Comparison<T>(T x, T y)はx,yの大小関係に応じて:

x < y なら 負
x == y なら 0
x > y なら 正

の値を返すものを与えます。

void IList<T>.PushHeap(Comparison<T> comp)

　末尾要素以外の全要素がヒープ化されたIList<T>に末尾要素を追加します。これにより、IList<T>の先頭要素が全要素中最大となります。

void IList<T>.PopHeap(Comparison<T> comp)

　ヒープ化されたIList<T>の最大要素を末尾に移動し、ヒープを修復します。

void IList<T>.MakeHeap(Comparison<T> comp)

　IList<T>の全要素をヒープ化します。

void IList<T>.SortHeap(Comparison<T> comp)

　ヒープ化されたIList<T>をソートします。

　この結果、IList<T>はcompで与えられた大小関係に基づき昇順にソートされます。

サンプル・コード

class Program {
  static void Main() {

    int[] input = { 5, 1, 3, 6, 7, 8, 9, 0, 2, 4 };
    List<int> lst = null;
    Comparison<int> comp = lst.DefaultComparison();

    /* 
     * PushHeap 
     */
    lst = new List<int>();
    foreach (int item in input) {
      lst.Add(item);
      lst.PushHeap(comp);
      lst.ForEach(x => Console.Write("{0} ", x));
      Console.WriteLine();
    }

    /* 
     * PopHeap
     */
    Console.WriteLine("pop descending...");
    while (lst.Count > 0) {
      lst.PopHeap(comp);
      int item = lst[lst.Count - 1];
      lst.RemoveAt(lst.Count - 1);
      lst.ForEach(x => Console.Write("{0} ", x));
      Console.WriteLine("|{0}", item);
    }

    /*
     * MakeHeap/SortHeap
     */
    lst = new List<int>(input);
    Console.WriteLine("sort ascending...");
    lst.MakeHeap(comp);
    lst.SortHeap(comp);
    lst.ForEach(item => Console.Write("{0} ", item));
    Console.WriteLine();
  }
}