你好，我学习了您讲解的算法之后自己按照算法写了C++的实现，包括插入，删除最小，删除最大的操作，但是在线评测总是出问题，个人检查认为是对的，您能帮忙指点一下，看看哪里错了吗？
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <stdlib.h>
#include <iostream>
using namespace std;
#define SIZE 110100

struct heap
{
public:
void init();
void insert(long long);
long long del_min();
long long del_max();

void fool_min_insert(long long,long long);
void fool_max_insert(long long,long long);
void min_push_down(long long&);
void max_push_down(long long&);

long long parent(long long n){return n/2;}
long long lchild(long long n){if(n*2<=size)return 2*n;else return 0;}
long long rchild(long long n){if(n*2+1<=size)return n*2+1;else return 0;}
bool is_min_heap(long long n)
{
while(n>3)n/=2;
if(n==2)return true;
else return false;
}
long long partner(long long n)
{
long long j=log((double)n)/log((double)2);
long long k=(long long)pow((double)2,(double)j)-1;
long long e=k^n;
if(e<=size)return e;
else return partner(parent(n));
}
void swap(long long &a,long long &b){long long temp=a;a=b;b=temp;}
private:
long long key[SIZE];
long long size;
};
void heap::init()
{
size=1;
memset(key,-1,sizeof(key));
}
void heap::fool_min_insert(long long k,long long pos)
{
key[pos]=k;
long long cur=pos;
while(parent(cur)>1)
{
if(key[parent(cur)]>key[cur])
{
swap(key[parent(cur)],key[cur]);
cur=parent(cur);
}
else break;
}
}
void heap::fool_max_insert(long long k,long long pos)
{
key[pos]=k;
long long cur=pos;
while(parent(cur)>1)
{
if(key[parent(cur)]<key[cur])
{
swap(key[parent(cur)],key[cur]);
cur=parent(cur);
}
else break;
}
}
void heap::insert(long long k)
{
size++;
if(size==2)
{
key[size]=k;
return;
}
if(is_min_heap(size))
{
long long j=partner(size);
if(k<=key[j])
fool_min_insert(k,size);
else
{
fool_min_insert(key[j],size);
fool_max_insert(k,j);
}
}
else
{
long long j=partner(size);
if(k>=key[j])
fool_max_insert(k,size);
else
{
fool_max_insert(key[j],size);
fool_min_insert(k,j);
}
}
}
void heap::min_push_down(long long& cur)
{
long long c;
while(lchild(cur)!=0)
{
c=cur;
if(lchild(cur)!=0)c=lchild(cur);
if(rchild(cur)!=0&&key[rchild(cur)]<=key[lchild(cur)])
c=rchild(cur);
key[cur]=key[c];
cur=c;
}
}
void heap::max_push_down(long long& cur)
{
long long c;
while(lchild(cur)!=0)
{
c=cur;
if(lchild(cur)!=0)c=lchild(cur);
if(rchild(cur)!=0&&key[rchild(cur)]>=key[lchild(cur)])
c=rchild(cur);
key[cur]=key[c];
cur=c;
}
}
long long heap::del_min()
{
if(size==1)return 0;
if(size==2)
{
size--;
return key[size+1];
}
long long e=key[2];
long long cur=2;
min_push_down(cur);
long long j=partner(cur);
long long value=key[size];
if(value<=key[j])
fool_min_insert(value,cur);
else
{
fool_min_insert(key[j],cur);
fool_max_insert(value,j);
}
size--;
return e;
}
long long heap::del_max()
{
if(size==1)return 0;
if(size==2)return key[size--];
long long e=key[3];
long long cur=3;
max_push_down(cur);
long long j=partner(cur);
long long value=key[size];
if(lchild(j)==size)j=lchild(j);
else if(rchild(j)<=size)
j=(key[lchild(j)]>key[rchild(j)])?lchild(j):rchild(j);
if(value>=key[j])
fool_max_insert(value,cur);
else
{
fool_max_insert(key[j],cur);
fool_min_insert(value,j);
}
size--;
return e;
}
int main()
{
heap h;
h.init();
long long n,pts;
char ch;
scanf("%lld",&n);
while(n-->0)
{
getchar();
scanf("%c",&ch);
if(ch=='I')
{
scanf("%lld",&pts);
h.insert(pts);
}
else if(ch=='H')
printf("%lld\n",h.del_max());
else if(ch=='L')
printf("%lld\n",h.del_min());
}
return 0;
}  回复  更多评论
  

@Cppowboy
是不是操作后，序列违反了双端堆的性质？我的代码是可以用的，当时做过很久的随机测试，都没有违反性质。  回复  更多评论
  

@Cppowboy
实现细节可以不同，我的实现与stl中的优先级队列类似，关键是各种操作后，保证序列不违反性质就行了。  回复  更多评论