using system;xml:namespace prefix = o />
using system.collections;
namespace datastructure
{
/// <summary>
/// binaryheap 的摘要说明。-------二叉堆(基于数组的实现)
/// </summary>
public class binaryheap:ipriorityqueue
{
protected arraylist array;
//建立一个最多容纳_length个对象的空二叉堆
public binaryheap(uint _length)
{
//
// todo: 在此处添加构造函数逻辑
//
array=new arraylist((int)_length);
array.capacity=(int)_length;
}
//堆中对象个数
public virtual int count{get{return this.array.count;}}
//将成员数组变成用1为基数表达的形式
public virtual object item(int _i)
{
if(_i>=this.array.capacity)
throw new exception("my:out of index");//不能出界
return this.array[_i-1];
}
#region ipriorityqueue 成员
//先将空洞放在数组的下一个位置上，也就是i(注：基数是1),然后和[i/2]位置上的数比较，如果小于则将空洞上移到[i/2]位置，而原先[i/2]位置上的对象则移到[i]上，否则就将空洞变为_obj----如此递归
public void enqueue(object _obj)
{
// todo: 添加 binaryheap.enqueue 实现
if( this.array.count==this.array.capacity )
throw new exception("my:priority queue is full");//如果优先队列已满，则抛出异常
this.array.add(new object());
int i=this.array.count;
while(i>1&&comparer.default.compare(this.array[i/2-1],_obj )>0)
{
//this.item(i)=this.item(i/2);
this.array[i-1]=this.array[i/2-1];
i/=2;
}
this.array[i-1]=_obj;
}
public object findmin()
{
// todo: 添加 binaryheap.findmin 实现
if( this.array.count==0 )
throw new exception("my:priority queue is empty");//如果队列是空的，则抛出异常
return this.array[0];
}
public object dequeuemin()
{
// todo: 添加 binaryheap.dequeuemin 实现
object tmpobj=this.findmin();
int i=1;
while( (2*i+1)<=this.array.count)
{
if( comparer.default.compare(this.array[2*i-1],this.array[2*i])<=0 )
{
this.array[i-1]=this.array[2*i-1];
this.array[2*i-1]=tmpobj;
i=2*i;
}
else
{
this.array[i-1]=this.array[2*i];
this.array[2*i]=tmpobj;
i=2*i+1;
}
}
object delobj=this.array[i-1];//暂时储存要删去的元素
if(i!=this.array.count)//如果搜索到的对象就是数组的最后一个对象，则什么都不要做
{
this.array[i-1]=this.array[this.array.count-1];//添补空洞
}
this.array.removeat(this.array.count-1);//将最后一个对象删除
return delobj;
}
#endregion
}
}
Java Asp PHP .Net XML C/C++ CGI VB Jsp J2ee J2se J2me EJB Servlet Tomcat Resin Struts Weblogic Eclipse ANT GUI JMS Web servise IDEA Webphere Hibernate Spring Jboss Applet Swing Socket Javamail Perl Ajax P2P 安全 模式 框架 测试 开源 游戏
Windows XP Windows 2000 Windows 2003 Windows Me Windows 9.x Linux UNIX 注册表 操作系统 服务器 应用服务器
