using System;
using System.Collections;

namespace DataStructure
{
    /// <summary>
    /// BinaryHeap 的摘要說(shuō)明。-------二叉堆(基于數(shù)組的實(shí)現(xiàn))
    /// </summary>
    public class BinaryHeap:IPriorityQueue
    {
         protected ArrayList array;
         //建立一個(gè)最多容納_length個(gè)對(duì)象的空二叉堆
         public BinaryHeap(uint _length)
         {
              //
              // TODO: 在此處添加構(gòu)造函數(shù)邏輯
              //
              array=new ArrayList((int)_length);
              array.Capacity=(int)_length;
         }         //堆中對(duì)象個(gè)數(shù)
         public virtual int Count{get{return this.array.Count;}
    }    //將成員數(shù)組變成用1為基數(shù)表達(dá)的形式
    public virtual object Item(int _i)
    {
         if(_i&gt;=this.array.Capacity)
         throw new Exception("My:out of index");//不能出界
         return this.array[_i-1];
    }
 
    #region IPriorityQueue 成員    //先將空洞放在數(shù)組的下一個(gè)位置上，也就是i(注：基數(shù)是1),然后和[i/2]位置上的數(shù)比較，如果小于則將空洞上移到[i/2]位置，而原先[i/2]位置上的對(duì)象則移到[i]上，否則就將空洞變?yōu)開obj----如此遞歸
    public void Enqueue(Object _obj)
    {
       // TODO: 添加 BinaryHeap.Enqueue 實(shí)現(xiàn)
       if( this.array.Count==this.array.Capacity )
           throw new Exception("My:priority queue is full");//如果優(yōu)先隊(duì)列已滿，則拋出異常
       this.array.Add(new object());
       int i=this.array.Count;
       while(i&gt;1&amp;&amp;Comparer.Default.Compare(this.array[i/2-1],_obj )&gt;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 實(shí)現(xiàn)
         if( this.array.Count==0 )
             throw new Exception("My:priority queue is empty");//如果隊(duì)列是空的，則拋出異常
         return this.array[0];
    }    public object DequeueMin()
    {
         // TODO: 添加 BinaryHeap.DequeueMin 實(shí)現(xiàn)
         object tmpObj=this.FindMin();
         int i=1;
         while( (2*i+1)&lt;=this.array.Count)
         {
             if( Comparer.Default.Compare(this.array[2*i-1],this.array[2*i])&lt;=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];//暫時(shí)儲(chǔ)存要?jiǎng)h去的元素         if(i!=this.array.Count)//如果搜索到的對(duì)象就是數(shù)組的最后一個(gè)對(duì)象，則什么都不要做
         {
             this.array[i-1]=this.array[this.array.Count-1];//添補(bǔ)空洞
         }
         this.array.RemoveAt(this.array.Count-1);//將最后一個(gè)對(duì)象刪除
         return delObj;
     }     #endregion
 }
}