数据结构与算法C#实现---二叉堆（数组实现） -pc6资讯

您的位置：首页 → 精文荟萃 → 软件资讯 → 数据结构与算法C#实现---二叉堆（数组实现）

数据结构与算法C#实现---二叉堆（数组实现） 时间：2004/10/7 19:14:00来源：本站整理作者：蓝点我要评论(0)

using System;
using System.Collections;

namespace DataStructure
{
///

/// BinaryHeap 的摘要说明。-------二叉堆(基于数组的实现)
///

    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
}
}

文章评论

查看所有0条评论>>