学过数据结构的都知道优先队列这种东西，普通的队列是依据入队顺序，先入队的先出队，而优先队列则是依照键值，键值越大（或越小），就越先出队。
所以，优先队列基本支持push，pop，empty，size，top，这几种操作。最近在看C++prime，学了类之后觉得非常适合用来实现高级数据结构，于是就动手做了一下，花了一周，终于弄好了。以下的实现都默认最小堆。
二叉堆：
最常用，最简单的堆实现，因为二叉堆是完全二叉树，所有可以使用顺序存储结构，也就是说，数组来保存数据。二叉堆主要基于上滤与下滤操作来维持堆序（任意节点大与等于或小于等于他的子节点）而完全二叉树基本是平衡树，所以这些操作都是log2 N的时间复杂度，最后顺便一提，二叉堆可用于实现堆排序的算法。
#include <iostream>
#include <vector> class Bheap{//默认最小堆
public:
typedef int Element;
Bheap(const Element &Most);
Bheap(Element *arr, int size, const Element &Most);
~Bheap();
void push(const Element &e);
void pop();
bool empty();
const Element& top();
unsigned size();
void sort();
private:
std::vector<Element> data;
Element MostEle;
void PercolateDown(int loca);
void PercolateUp(int loca);
}; void Bheap::PercolateDown(int loca){
unsigned j;
Element cur = data[loca];
for (j = loca; j*<size();){
j *=;
if (j + < size() && data[j + ] < data[j]){
j++;
}
if (data[j]<cur)
data[j / ] = data[j];
else{
j /= ;
break;
}
}
data[j] = cur;
}
void Bheap::PercolateUp(int loca){
Element e = data[loca];
while (){
if (e<data[loca /]){
data[loca] = data[loca / ];
loca /=;
}
else{
break;
}
}
data[loca] = e;
}
Bheap::~Bheap()
{
}
Bheap::Bheap(Element *arr, int size, const Element &Most) :data(, Most), MostEle(Most){
for (int i = ; i < size; i++){
data.push_back(arr[i]);
}
for (int i = ((this->size()) /); i > ; i--){
PercolateDown(i);
}
}
Bheap::Bheap(const Element& Most) : data(, Most), MostEle(Most)
{
}
void Bheap::push(const Element &e){
data.push_back(e);
PercolateUp(data.size() - );
}
void Bheap::pop(){
data[] = data[data.size() - ];
PercolateDown();
data.pop_back();
}
bool Bheap::empty(){
return data.size() <= ;
}
const Bheap::Element& Bheap::top(){
return data[];
}
unsigned Bheap::size(){
return data.size() - ;
}
void Bheap::sort(){
for (int i = data.size() - ; i > ; i--){
Element t = data[];
data[] = data[i];
data[i] = t;
int j;
Element cur = data[];
for (j = ; j * <i;){
j *=;
if (j + < i && data[j + ] < data[j]){
j++;
}
if (data[j]<cur)
data[j / ] = data[j];
else{
j /= ;
break;
}
}
data[j] = cur;
}
}
左式堆：
左式堆是一颗二叉树，一般来说，我们更都喜欢平衡的树，平衡的树深度小，各种操作起来效率都更高，但是，左式堆却反其道而行之，最求不平衡的树，在实现avl树时，我们使用了左右子树的深度来作为树是否“比较平衡”的指标，而在左式堆中，我们也有类似的指标，npl（NULL path length），规定子节点数为0与1的节点的npl为0，空节点的npl为-1，任意节点的npl为他所有子节点中npl小的节点的npl+1。左式堆就是保持任意节点的左子树npl始终大于等于右子树的npl，这样的效果就是左子树始终比右子树深，虽然左子树深了，但是右子树就浅了啊，于是就可以大概保证push，pop操作为log2N，而且，不同于二叉堆，左式堆可以高效地支持合并操作，时间复杂度也是log2N左右，甚至，左式堆的所有操作都是基于合并操作。那么具体是怎么合并呢？因为是堆，于是保持着堆序，对于两个左式堆，我们比较根处的值，将小的堆的右子树与大的堆合并，并作为小的堆新的右子树，并且要更新npl，并根据npl决定是否交换子树，上面说过，左子树深了，右子树就浅了，于是就不用担心递归实现会爆栈来，因为，右子树非常浅（不大于log2N），深到递归实现会爆栈所需的数据是夸张的，所有可以放心地递归实现，但是我用了堆栈做了非递归实现（说了那么多，你居然没有用递归）。
#include <iostream>
#include <vector>
#include <stack> class Lheap
{
private:
typedef int Element;
struct LheapNode
{
Element e;
LheapNode*left;
LheapNode*right;
int npl;
LheapNode();
~LheapNode();
void swapchild();
void renewnpl();
const LheapNode& operator = (const LheapNode&a);
};
LheapNode *node;
int Size;
void Merge1(Lheap &a);
public:
Lheap();
Lheap(const Element &E);
Lheap(const LheapNode* a);
Lheap(const Element *arr, int size);
~Lheap();
void Merge(const Lheap &a);
void pop();
const Element &top();
bool empty();
int size()const;
void push(const Element &E);
}; Lheap::LheapNode::LheapNode() :left(NULL), right(NULL), npl(){}
Lheap::LheapNode::~LheapNode(){
delete left;
delete right;
}
void Lheap::LheapNode::renewnpl(){
if (right){
if (left){
if (right->npl > left->npl){
swapchild();
}
npl = right->npl + ;
}
else{
swapchild();
npl = ;
}
}
else{
npl = ;
}
}
void Lheap::LheapNode::swapchild(){
LheapNode* t = left;
left = right;
right = t;
}
const Lheap::LheapNode& Lheap::LheapNode:: operator = (const LheapNode&a){
if (a.left){
if (left == NULL)
left = new LheapNode;
*left = *a.left;
}
if (a.right){
if (right == NULL)
right = new LheapNode;
*right = *a.right;
}
npl = a.npl;
e = a.e;
return *this;
} Lheap::Lheap() :node(NULL),Size()
{
}
Lheap::Lheap(const Element *arr, int size) : node(NULL), Size()
{
node = new LheapNode;
node->e = arr[];
for (int i = ; i < size; i++)
push(arr[i]);
}
Lheap::Lheap(const Element &E) : node(NULL), Size(){
node = new LheapNode;
node->e = E;
}
Lheap::~Lheap()
{
delete node;
}
bool Lheap::empty(){
return node == NULL;
}
void Lheap::Merge1(Lheap &a){
if (node == NULL){
node = a.node;
a.node = NULL;
return;
}
std::stack<LheapNode*> s;
s.push(node);
LheapNode *b = a.node,*t;
while (){
if (s.top()->e < b->e){
if (s.top()->right){
s.push(s.top()->right);
}
else{
break;
}
}
else{
if (b->right){
t = s.top();s.pop();
s.push(b);
b = t;
s.push(s.top()->right);
}
else{
t = s.top();s.pop();
s.push(b);
b = t;
break;
}
}
}
while (!s.empty()){
t = s.top(); s.pop();
t->right = b;
b = t;
b->renewnpl();
}
node = b;
a.node = NULL;
}
void Lheap::Merge(const Lheap &a){
Lheap t;
t.node = new LheapNode;
*t.node = *a.node;//此处可根据需要选择是否要保留被并入的堆，不需要的话直接Merge1（a)就好了
Merge1(t);
Size += a.Size;
}
void Lheap::push(const Element &E){
Lheap t(E);
Merge1(t);
Size++;
}
void Lheap::pop(){
LheapNode *L = node->left,*R=node->right;
node->left = node->right =NULL;
delete node;
node = L;
if (R){
Lheap t;
t.node = R;
Merge1(t);
}
Size--;
}
const Lheap::Element& Lheap::top(){
return node->e;
}
int Lheap::size()const{
return Size;
}
二项队列：
二项树，是一种特殊的树，他的特点是，我们把一棵有2^k个节点的树叫做K树，k树有k-1个子树，分别是0到k-1树，而二项队列就是按k树k值大小排列的队列（说好的队列呢），此外，二项队列有一个最大的特点，那就是每种树都只能存在一棵，如果存在两颗呢？那我们就要将他们合并为一棵树，比如说，如果有两颗0树，那么，我们就要将他们合并为一棵1树，怎么合并呢？想想，我们要构造的是堆，于是二项树就必须符合堆序，那我们就只要将根值大的作为小的的子树。说到这些，有没有觉得熟悉呢？我们看一下二进制的加法，
1001 8+0+0+1
0011 0+0+2+1
1100 8+4+0+0
明白了吧，二项队列的具体结构与插入的值无关，虽然他是个堆，但是他长得怎么样，和你给他什么值没什么关系，很奇怪对不对，但真的是这样，二项队列的结构取决于插入元素的个数。二项队列的特质，使他唯一对应于一个二进制数字，于是我们可以利用两个堆大小对应二进制数字的加法来控制流程。然后，我们对它的操作做分析，首先对合并操作进行分析，首先，我们知道，对于一个有N个元素的二项队列，长度不超过Log2N，因为，一个二项队列对应一个二进制整数。合并相当于一次加法运算，二项队列的合并就是对其队列中的二项树自小到大进行合并，插入下一位的操作（进位），那么复杂度是O（log2N），pop操作则是在队列中寻找根最小的二项树（花费Log2N），将其子树当成新队列，与除去了二项队列中该树，再将该队列与新队列合并，操作也是log2N，最后，就是push操作，二项队列最大的特点就是，虽然不能保证每次操作都是o（1）的时间复杂度，但是可以保证M次push操作，平均的时间复杂度是（1 ),为什么呢？我们来分析一下，对于push操作，相当于一个二项队列与对应1的二项队列相加。首先，先明白这样一件事，push操作花费的时间取决于二项队列结尾出现第一个0之前1的个数，比如说，00就只需要一次插入，01就需要一次插入，一次合并，011就需要一次插入，两次合并，假设一个二项队列在进行push操作前大小是k，通过M次插入操作变为k+M，该过程中，最低位为1的概率有1/2，于是有一半的数需要一次合并，而显然剩下的树不需要再合并，然后在这一半的数中，又有一半的数第二位为1，他们需要第二次合并，而另一半则不需要，依此类推，从k到k+M-1这M个数，所需合并次数为 M/2+M/4+M/8....+1，假设M为偶数（因为奇数结果也差不了多少），则为M（1/2+1/4+。。。+1/M)=M-1,此外，每次操作无论合并几次，都要插入一次，于是M-1次合并，M次插入，平均需要O（M-1+M) / M = O（1）的时间复杂度。这种分析方式就是所谓的摊还分析了，有的数据结构，比如伸展树，比如斜堆，都有虽然不能保证每次操作是O（x），但是能保证M次操作为O（Mx）的特点，这种分析比较复杂，我到现在都不是很会，于是你会发现我在分析上面两种实现时草草带过，二叉堆是因为真的没有什么好说的，左式堆是因为我真的没有什么会说的。。。还是好好学习一下怎么进行摊还分析吧。另外，优先队列的实现中没有斜堆，因为他和左式堆差不多，区别就像AVL树与伸展树差不多，他不会通过npl这种东西来判断是否交换子树，他只是简单粗暴地交换每个合并的节点的子树。。。。最后吐槽一下，说好的队列，结果我使用deque来作为队列，但最后才发现，直接开个32大小的数组反而比较实在，毕竟可以存2^31大约10亿个数据了，对于我这种没见过世面的人来说已经妥妥的了。
#include <iostream>
#include <vector>
const int Default_size=;
class Bqueue
{
private:
typedef int Element;
struct BtreeNode
{
BtreeNode*child;
BtreeNode*sibling;
Element data;
BtreeNode();
~BtreeNode();
};
typedef BtreeNode * Btree;
std::vector<Btree> q;
int Size;
public:
Bqueue();
Bqueue(int size);
Bqueue(Element *arr, int size);
~Bqueue();
void push(const Element &e);
void pop();
Bqueue& Merge(Bqueue &Q);
int size()const;
const Element& top()const;
bool empty()const;
Btree combineTree(Btree T1, Btree T2)const;
}; Bqueue::BtreeNode::BtreeNode():child(NULL), sibling(NULL){}
Bqueue::BtreeNode::~BtreeNode(){
delete child;
delete sibling;
} Bqueue::Bqueue() :Size(){
q.resize(Default_size);
}
Bqueue::Bqueue(int size) : Size(size){
q.resize(Default_size);
}
Bqueue::~Bqueue(){
for (std::vector<Btree>::iterator p = q.begin(); p != q.end(); p++)
delete *p;
}
Bqueue& Bqueue::Merge(Bqueue &Q){
Btree T1, T2,Carry=NULL;
Size += Q.size();
for (int i = , j = ;j<=Size; i++, j *= ){
T1 = q[i]; T2 = Q.q[i];
switch (!!T1+*!!T2+*!!Carry)
{
case :
case :
break;
case :
q[i] = T2;
Q.q[i] = NULL;
break;
case :
Carry = combineTree(T1, T2);
q[i] = Q.q[i] = NULL;
break;
case :
q[i] = Carry;
Carry = NULL;
break;
case :
Carry = combineTree(T1, Carry);
q[i] = NULL;
break;
case :
Carry = combineTree(Carry, T2);
Q.q[i] = NULL;
break;
case :
q[i] = Carry;
Carry = combineTree(T1, T2);
Q.q[i] = NULL;
break;
default:
break;
}
}
return *this;
}
int Bqueue::size()const{
return Size;
}
void Bqueue::push(const Element &e){
Btree T = new BtreeNode,T1;
T->data = e;
Size += ;
for (int i = ,j=; j <= Size&&T; i++,j*=){
T1 = q[i];
switch (!!T*+!!T1){
case :
q[i] = T;
T = NULL;
break;
case :
q[i] = NULL;
T=combineTree(T, T1);
break;
default:
break;
}
}
}
void Bqueue::pop(){
int i, j, Mintree=;
Btree DeletedTree, Oldroot;
while (q[Mintree]==NULL)
{
Mintree++;
}
for (i = Mintree+, j = <<i; j <= Size; j *= ,i++)
if (q[i])
Mintree = q[Mintree]->data<q[i]->data?Mintree:i;
Oldroot = DeletedTree = q[Mintree];
DeletedTree = DeletedTree->child;
Oldroot->child = NULL;
delete Oldroot;
Bqueue DeleteQueue(( << Mintree) - );
for (i = Mintree - ; i >= ; i--){
DeleteQueue.q[i] = DeletedTree;
DeletedTree = DeletedTree->sibling;
DeleteQueue.q[i]->sibling = NULL;
}
q[Mintree] = NULL;
Size -= DeleteQueue.size() + ;
Merge(DeleteQueue);
}
bool Bqueue::empty()const{
return Size == ;
}
const Bqueue:: Element& Bqueue::top()const{
int res=;
while (q[res] == NULL)
{
res++;
}
for (int i = res + , j = << i; j <= Size; j *= , i++)
if (q[i])
res = q[res]->data<q[i]->data ? res : i;
return q[res]->data;
}
Bqueue::Btree Bqueue::combineTree(Btree T1,Btree T2)const{
if (T1->data > T2->data)
return combineTree(T2, T1);
T2->sibling = T1->child;
T1->child = T2;
return T1;
}
最后，我们实际看一下各种实现的效果，我们用合并果子这道经典贪心算法来测试一下。
二叉堆：
- 测试点1 Accepted / 1ms / 12396kB
- 测试点2 Accepted / 2ms / 12396kB
- 测试点3 Accepted / 2ms / 12396kB
- 测试点4 Accepted / 19ms / 12396kB
- 测试点5 Accepted / 18ms / 12396kB
- 测试点6 Accepted / 51ms / 12396kB
- 测试点7 Accepted / 50ms / 12396kB
- 测试点8 Accepted / 45ms / 12396kB
- 测试点9 Accepted / 53ms / 12396kB
- 测试点10 Accepted / 50ms / 12396kB
STL 的优先队列《vector》
- 测试点1 Accepted / 5ms / 12400kB
- 测试点2 Accepted / 8ms / 12400kB
- 测试点3 Accepted / 14ms / 12400kB
- 测试点4 Accepted / 36ms / 12400kB
- 测试点5 Accepted / 45ms / 12400kB
- 测试点6 Accepted / 85ms / 12400kB
- 测试点7 Accepted / 84ms / 12400kB
- 测试点8 Accepted / 80ms / 12400kB
- 测试点9 Accepted / 85ms / 12400kB
- 测试点10 Accepted / 87ms / 12400kB
二项队列：
- 测试点1 Accepted / 3ms / 12396kB
- 测试点2 Accepted / 17ms / 12396kB
- 测试点3 Accepted / 20ms / 12396kB
- 测试点4 Accepted / 77ms / 12396kB
- 测试点5 Accepted / 101ms / 12528kB
- 测试点6 Accepted / 202ms / 12660kB
- 测试点7 Accepted / 196ms / 12660kB
- 测试点8 Accepted / 195ms / 12660kB
- 测试点9 Accepted / 211ms / 12660kB
- 测试点10 Accepted / 190ms / 12660kB
左式堆：
- 测试点1 Accepted / 2ms / 12400kB
- 测试点2 Accepted / 29ms / 12400kB
- 测试点3 Accepted / 30ms / 12400kB
- 测试点4 Accepted / 143ms / 12528kB
- 测试点5 Accepted / 164ms / 12528kB
- 测试点6 Accepted / 391ms / 12784kB
- 测试点7 Accepted / 379ms / 12784kB
- 测试点8 Accepted / 381ms / 12784kB
- 测试点9 Accepted / 376ms / 12784kB
- 测试点10 Accepted / 357ms / 12784kB
可以看出，简单除暴的二叉堆效率是最高的，左式堆最不给力。。。
以上代码参考自《数据结构与算法分析:c语言描述》