re: 基于雙端堆實(shí)現(xiàn)的優(yōu)先級(jí)隊(duì)列(2): 內(nèi)幕
2014-01-05 10:06 |
你好，我學(xué)習(xí)了您講解的算法之后自己按照算法寫(xiě)了C++的實(shí)現(xiàn)，包括插入，刪除最小，刪除最大的操作，但是在線(xiàn)評(píng)測(cè)總是出問(wèn)題，個(gè)人檢查認(rèn)為是對(duì)的，您能幫忙指點(diǎn)一下，看看哪里錯(cuò)了嗎？
#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;
}
回復(fù) 更多評(píng)論