共有回帖数 0 个
-
Double-Ended Heap（Deap，双端堆）是一种 double-ended priority queue（双端优先队列），它是最小堆和最大堆的结合体，即既支持获取最小关键字的操作，又能获取最大关键字，并能进行删除。它的根是一个没有关键字的结点，左边是一个最小堆，右边是一个最大堆。它的高度的界为 Θ(log n)，插入、删除关键字的时间复杂度均为 Ο(log n)。
下面是 Double-Ended Heap 的实现：
#include vector
template typename Type
class DoubleEndedHeap
{
public:
typedef Type key_type;
typedef size_t size_type;
DoubleEndedHeap() : n(1) {}
explicit DoubleEndedHeap(size_type size) : n(1)
{
a.resize(size+2);
}
bool empty() const
{
return n == 1;
}
void insert(const key_type &key);
void pop_max();
void pop_min();
const key_type &top_max() const
{
return n == 2 ? a[2] : a[3];
}
const key_type &top_min() const
{
return a[2];
}
private:
size_type high_bit(size_type x) const
{
while (x != (x & -x))
x -= x & -x;
return x;
}
void insert_max(size_type pos, const key_type &key)
{
for (; pos = 6 && a[pos/2] key; pos /= 2)
a[pos] = a[pos/2];
a[pos] = key;
}
void insert_min(size_type pos, const key_type &key)
{
for (; pos = 4 && key a[pos/2]; pos /= 2)
a[pos] = a[pos/2];
a[pos] = key;
}
size_type n;
std::vectorkey_type a;
};
template typename Type
void DoubleEndedHeapType::insert(const key_type &key)
{
if (++n = a.size()) a.resize(n*2);
if (n == 2)
{
a[2] = key;
return;
}
size_type i = n ^ high_bit(n)/2;
if ((n/2 ^ n) n)
{ //min side
if (i n) i /= 2;
if (key a)
insert_min(n, key);
else
{
a[n] = a;
insert_max(i, key);
}
}
else
{ //max side
if (a key)
insert_max(n, key);
else
{
a[n] = a;
insert_min(i, key);
}
}
}
template typename Type
void DoubleEndedHeapType::pop_max()
{
if (n 4)
{
--n;
return;
}
size_type i, j;
a[1] = a[n--];
for (i = 3; i*2 = n; )
{
if (i*2 n && a[i*2] a[i*2+1])
a = a[i*2+1], i = i*2+1;
else
a = a[i*2], i *= 2;
}
j = i-high_bit(i)/2;
if (j*2 = n)
{
j *= 2;
if (j n && a[j] a[j+1]) ++j;
}
if (a[1] a[j])
{
a = a[j];
insert_min(j, a[1]);
}
else
insert_max(i, a[1]);
}
template typename Type
void DoubleEndedHeapType::pop_min()
{
size_type i, j;
a[1] = a[n--];
for (i = 2; i*2 = n; )
{
if (i*2 n && a[i*2+1] a[i*2])
a = a[i*2+1], i = i*2+1;
else
a = a[i*2], i *= 2;
}
j = i+high_bit(i)/2;
if (j n) j /= 2;
if (a[j] a[1]) //j may be 1
{
a = a[j];
insert_max(j, a[1]);
}
else
insert_min(i, a[1]);
}
楼主 2016-01-08 10:35 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
