BinaryHeap

mybinaryheap.d

// - Test
//   dmd mybinaryheap.d -main -unittest [-cov]
//   ./mybinaryheap
// 
// - import
//   import mybinaryheap : MyBinaryHeap

module mybinaryheap;

unittest
{
  int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
  auto h = new MyBinaryHeap!(int, "a>b")(a);
  assert(h.front == 16);
  h.insert(20);
  assert(h.front == 20);
  h.removeFront;
  h.removeFront;
  assert(h.front == 14);
  assert(!h.empty);
}

unittest
{
  import std.container.binaryheap : BinaryHeap;

  int[] a = [3, 9, 17, 8, 19, 4, 19, 16, 4, 8, 14, 6, 18, 12, 18, 14, 15, 9,
    12, 5, 1, 13, 1, 11, 16, 1, 3, 17, 3, 13];
  auto b = a.dup;
  auto h = new BinaryHeap!(int[])(a, a.length);
  auto h2 = new MyBinaryHeap!(int, "a>b");
  foreach (x; b)
    h2.insert(x);
  foreach (_; 0 .. b.length)
  {
    assert(h.front == h2.front);
    h.removeFront;
    h2.removeFront;
  }
  assert(h2.empty);
}

import std.functional : binaryFun;

class MyBinaryHeap(T, alias less = "a<b")
    if (is(typeof(binaryFun!less(T.init, T.init))))
{
  import std.range.primitives : _front = front, _back = back, _empty = empty,
    popBack;
  import std.exception : enforce;
  import std.algorithm.iteration : each;
  import std.algorithm.mutation : swap;

  private T[] dat;
  private alias comp = binaryFun!(less);

  this(T[] arr = [])
  {
    arr.each!(x => insert(x));
  }

  void insert(T x)
  {
    size_t i = dat.length;
    dat ~= x;
    while (i > 0)
    {
      size_t p = (i - 1) / 2;
      if (comp(dat[i], dat[p]))
      {
        swap(dat[i], dat[p]);
        i = p;
      }
      else
      {
        break;
      }
    }
  }

  T front()
  {
    enforce(dat.length > 0, "Cannot call front on an empty heap.");
    return dat._front;
  }

  void removeFront()
  {
    enforce(dat.length > 0, "Cannot call removeFront on an empty heap.");
    swap(dat._front, dat._back);
    dat.popBack;
    size_t len = dat.length;
    size_t i = 0;
    while (i * 2 + 1 < len)
    {
      if (i * 2 + 2 < len)
      {
        // 左右で強いほうの子と比べる
        size_t j = comp(dat[i * 2 + 1], dat[i * 2 + 2]) ? i * 2 + 1 : i * 2 + 2;
        if (comp(dat[j], dat[i]))
        {
          swap(dat[j], dat[i]);
          i = j;
        }
        else
        {
          break;
        }
      }
      else // 左の子しかない
      {
        if (comp(dat[i * 2 + 1], dat[i]))
        {
          swap(dat[i * 2 + 1], dat[i]);
          i = i * 2 + 1;
        }
        else
        {
          break;
        }
      }
    }
  }

  bool empty()
  {
    return dat._empty;
  }
}