二叉堆

一个最小二叉堆的 C++ 实现，底层采用了数组形式的 Vector 结构存放二叉树。add 添加元素到堆，shift 从堆顶部删除元素，peek 获取堆顶部元素。其中最重要的算法是 bubble-down，它把堆中放置位置过高的“重”（如果是最大堆，自然就是“轻”）物推到了合适位置。二叉堆再抽象一层，就可以用来实现优先队列。

#ifndef _BINARY_HEAP_H_
#define _BINARY_HEAP_H_

#include <vector>

template <typename T>
class BinaryHeap
{
public:
    BinaryHeap()
    {
    }

    BinaryHeap(const T& elem)
    {
        heap_.push_back(elem);
    }

    BinaryHeap(const std::vector<T>& elems)
    {
        heap_= elems;
        for (int i = (heap_.size() - 1) / 2; i >= 0; --i)
            bubbleDown(i);
    }

    virtual void insert(const T& elem)
    {
        int i = heap_.size();
        heap_.resize(i + 1);
        do {
            /* Check heap_[i]'s parent. */
            int j = (i - 1) / 2;
            if (i <= 0 || elem >= heap_[j])
                break;
            heap_[i] = heap_[j];
            i = j;
        } while (true);
        heap_[i] = elem;
    }

    virtual T shift(unsigned idx = 0)
    {
        if (heap_.size() <= idx)
            throw "Heap is empty";
        T ret = heap_[idx];
        heap_[idx] = heap_.back();
        heap_.pop_back();
        bubbleDown(idx);
        return ret;
    }

    virtual const T& peek() const
    {
        return heap_.front();
    }

    virtual BinaryHeap<T>& operator << (const T& elem)
    {
        insert(elem);
        return *this;
    }

    virtual BinaryHeap<T>& operator >> (T& receiver)
    {
        receiver = shift();
        return *this;
    }

protected:
    void bubbleDown(unsigned idx)
    {
        unsigned int max = idx;
        do {
            unsigned int i, j;
            i = idx * 2 + 1;
            j = i + 1;
            /* Pick heap_[i]'s largest child. */
            if (j < heap_.size() && heap_[j] < heap_[max])
                max = j;
            if (i < heap_.size() && heap_[i] < heap_[max])
                max = i;
            if (max == idx)
                break;
            /* Exchange heap_[i] and heap_[max_idx]. */
            T tmp = heap_[idx];
            heap_[idx] = heap_[max];
            heap_[max] = tmp;
            idx = max;
        } while (true);
    }

protected:
    std::vector<T> heap_;
};

#endif /* _BINARY_HEAP_H_ */

同样的算法也用 Ruby 写了一份，但执行效率是有巨大差别的，特别是 Ruby 1.8。不过使用 Ruby 的好处是通过闭包可以方便地传递匿名比较函数，而在 C++ 中则需要传递函数指针，这个过程往往缺乏爱且伴随着痛苦。

class BinaryHeap
  def initialize(*args, &cmptr)
    @cmptr = cmptr
    @heap = args.clone
    i = (@heap.size - 1) >> 1
    while i >= 0
      bubble_down(i)
      i -= 1
    end
  end
  def insert(elem)
    i = @heap.size
    loop do
      j = (i - 1) >> 1
      if j < 0 || @cmptr.call(elem, @heap[j]) <= 0
        @heap[i] = elem
        break
      else
        @heap[i] = @heap[j]
        i = j
      end
    end
    self
  end
  def shift(idx = 0)
    ret = @heap[idx]
    len = @heap.size
    if len > 1
      @heap[idx] = @heap.pop
      bubble_down(idx)
    elsif 1 == len
      @heap.clear
    end
    ret
  end
  def bubble_down(idx)
    len = @heap.size
    loop do
      i = (idx << 1) + 1
      j = i + 1
      max = idx
      max = j if j < len && @cmptr.call(@heap[j], @heap[max]) > 0
      max = i if i < len && @cmptr.call(@heap[i], @heap[max]) > 0
      if max != idx
        @heap[idx],@heap[max] = @heap[max],@heap[idx]
        idx = max
      else
        break
      end
    end
  end
  def to_s(indent = 8)
    helper = lambda do |idx, acc|
      if idx >= @heap.size then ''
      else
        child_base = idx << 1
        helper.call(child_base + 2, acc + 1) +
        ' '*indent*acc + @heap[idx].to_s + "\n" +
        helper.call(child_base + 1, acc + 1)
      end
    end
    helper.call(0, 0)
  end
  def <<(elem)
    add(elem)
  end
end

DATA = 10
data = Array.new(DATA)
DATA.times do |i|
  data[i] = rand(DATA<<1)
end

bh = BinaryHeap.new(*data) { |a, b| a <=> b }
print bh
bh << 1 << 3 << 0 << -3 << 0
print bh
bh.shift
print bh
bh.shift
print bh