从实现的角度来说, 使用完全二叉树作为堆的前提的好处是, 完全二叉树非常容易实现, 甚至可以说是最容易实现的二叉树. 由于完全二叉树的节点编号是连续的, 那么它可以被拉平, 放进一个日常的数组中, 如
+---+
| 4 |
+---+
/ \
+---+ +---+
| 5 | | 9 |
+---+ +---+
/ \
+---+ +---+
| 8 | | 5 |
+---+ +---+
.----.
/--. \
+---+---+---+---+---+---+-----
| - | 4 | 5 | 9 | 8 | 5 | ...
+---+---+---+---+---+---+-----
\______/ /
\________/
.----.
/--. \
+---+---+---+---+---+---+-----
| 0 | 1 | 2 | 3 | 4 | 5 | ...
+---+---+---+---+---+---+-----
\______/ /
\________/
.----.
/--. \
+---+---+---+---+---+---+-----
| - | 0 | 1 | 2 | 3 | 4 | ...
+---+---+---+---+---+---+-----
\______/ /
\________/
i << 1, 2i+1 等效于 (i << 1) | 1, floor(i/2) 等效于 i >> 1, 这还能提供一丁点效率优化 (和一部分代码混乱程度加成, 以及大量的极客自豪感上升).既然堆的逻辑结构是数组, 那么可以采用
std::vector 作为存储数据结构. 此外, 将比较方式以模板形式抽出, 这样可以构造一个抽象的最值堆, 而不是死板的最大堆或者最小堆. 下面是堆的框架template <typename _T, typename _Less>
class heap {
std::vector<_T> array;
_Less const less;
typedef typename std::vector<_T>::size_type size_type;
public:
heap()
: array(1) /* insert a placeholder, array[0] */
, less(_Less())
{}
void push(_T const& value);
_T pop();
};
template <typename _T, typename _Less>
class heap {
std::vector<_T> array;
_Less const less;
typedef typename std::vector<_T>::size_type size_type;
public:
heap()
: array(1)
, less(_Less())
{}
void push(_T const& value)
{
array.push_back(value);
shift_up(array.size() - 1);
}
_T pop();
private:
void shift_up(size_type index)
{
size_type parent_index = index >> 1;
if (index != 1 && less(array[index], array[parent_index])) {
std::swap(array[index], array[parent_index]);
shift_up(parent_index);
}
}
};
_Less 类型含有函数bool operator()(_T const& lhs, _T const& rhs) const;返回值表示前面的参数是否小于后一个参数.
接下来是弹出最值, 因为向更深层移动节点会牵扯到很多索引越界的检查, 因此代码看起来会繁琐一些. 仍然采用递归实现
template <typename _T, typename _Less>
class heap {
std::vector<_T> array;
_Less const less;
typedef typename std::vector<_T>::size_type size_type;
public:
heap()
: array(1)
, less(_Less())
{}
void push(_T const& value)
{
array.push_back(value);
shift_up(array.size() - 1);
}
_T pop()
{
_T result = array[1];
std::swap(array[1], array.back());
array.pop_back();
shift_down(1);
return result;
}
private:
void shift_up(size_type index)
{
size_type parent_index = index >> 1;
if (index != 1 && less(array[index], array[parent_index])) {
std::swap(array[index], array[parent_index]);
shift_up(parent_index);
}
}
void shift_down(size_type index)
{
size_type lchild_index = index << 1;
size_type rchild_index = (index << 1) | 1;
if (array.size() <= index || array.size() <= lchild_index) {
return;
}
size_type min_child_index = 0;
if (array.size() <= rchild_index) {
min_child_index = lchild_index;
} else {
min_child_index = less(array[lchild_index], array[rchild_index])
? lchild_index : rchild_index;
}
if (less(array[min_child_index], array[index])) {
std::swap(array[min_child_index], array[index]);
shift_down(min_child_index);
}
}
};
std::priorty_queue), 它除了像上述实现的堆支持数据类型和比较方式两个模板参数, 还能设置底层数据结构 (默认为 std::vector), 其声明为template <typename _Tp
, typename _Sequence = std::vector<_Tp>
, typename _Compare = std::less<typename _Sequence::value_type> >
class std::priority_queue;
std::priority_queue<int> heap;
heap.push(1);
heap.push(2);
heap.push(0);
std::cout << heap.top() << std::endl;
typedef std::priority_queue<int, std::vector<int>, std::greater_equal<int> > minheap;堆可以以很均衡的代价从一个动态集合中获得最值, 但是这还不够拉风, 怎么改进一下, 能够以差不多均衡的代价从一个动态集合中取得第 K 最小值呢?
一个堆干这个事情可能很困难, 那么就来两个吧. 将一个最大堆和一个最小堆放在一起, 并且将较小的 K 个元素维护在最大堆中, 其它元素放入最小堆, 这时最小堆的堆顶就是第 K 最小值了. 还是用
std::priority_queue 而不是之前文中实现的山寨货来构造这样一个玩意儿/* binary_function 逆转 adaptor
将 binary_function 得到的返回值求非并返回 */
template <typename _Tp, typename _CompareBinaryFn>
struct binary_negate {
_CompareBinaryFn fn;
binary_negate()
: fn(_CompareBinaryFn())
{}
explicit binary_negate(_CompareBinaryFn const& f)
: fn(f)
{}
bool operator()(_Tp const& lhs, _Tp const& rhs)
{
return !fn(lhs, rhs);
}
};
template <typename _Tp, unsigned _K, typename _Compare>
class kth_heap {
/* 较小的一堆数量为 _K 的元素, 放置在最大堆中 */
std::priority_queue<_Tp, std::vector<_Tp>, _Compare > lessers;
/* 较小的一堆元素, 放置在最小堆中 */
std::priority_queue<_Tp, std::vector<_Tp>, binary_negate<_Tp, _Compare> > greaters;
public:
void push(_Tp const& value)
{
lessers.push(value);
if (_K < lessers.size()) {
greaters.push(lessers.top());
lessers.pop();
}
}
_Tp pop()
{
_Tp result(greaters.top());
greaters.pop();
return result;
}
};
/* 特化 _K 为 0, 也就是单纯的最小堆的情形 */
template <typename _Tp, typename _Compare>
class kth_heap<_Tp, 0, _Compare>
{
std::priority_queue<_Tp, std::vector<_Tp>, binary_negate<_Tp, _Compare> > heap;
public:
void push(_Tp const& value)
{
heap.push(value);
}
_Tp pop()
{
_Tp result(heap.top());
heap.pop();
return result;
}
};
