Data Structure and Algorithm (C # Implementation) Series --- Fifty Heap (Array Implementation)
Using system;
Using system.collections;
Namespace Datastructure
{
///
/// binary Heap Summary Description. ------ binary pile (based on array implementation)
///
Public class binaryheap: ipriorityQueue
{
protected arraylist array;
// Establish a maximum of the empty two fork pile of most accommodation_length
Public binaryHeap (uint _length)
{
//
// TODO: Add constructor logic here
//
Array = new arraylist (int) _length);
Array.capacity = (int) _length;
}
// number of objects in the heap
Public virtual int count {get {returnid.Array.count;}}
// Turn the member array into a form that is expressed in 1
Public Virtual Object Item (int _i)
{
IF (_i> = this.Array.capacity)
Throw new Exception ("my: out of index"); // cannot be out of bound
Return this.Array [_i-1];
}
#Region iPriorityQueue member
// First put the hole in the next position of the array, that is, i (Note: Boundary is 1), then compares with the [I / 2] position, if it is smaller, the cavity is moved to [I / 2 ] Location, and the object in the [I / 2] position is moved to [i], otherwise the empty hole becomes _obj ---- so recursive
Public void enqueue (Object _obj)
{
// Todo: Add binaryheap.enqueue implementation
IF (this.Array.count == this.Array.capacity)
Throw new Exception ("my: priority queue is full"); // If the priority queue is full, the exception is thrown
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: Add binaryheap.findmin implementation
IF (this.Array.count == 0)
Throw new exception ("my: priority quilt"); // If the queue is empty, throw an exception
Return this.Array [0];
}
Public Object DequeUemin ()
{
// Todo: Add binaryHeap.dequeueustry implementation
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]; // temporarily store the elements you want to delete
IF (i! = this.Array.count) // If the search object is the last object of the array, let not do anything
{
THIS.Array [i-1] = this.Array [this.Array.count-1]; // Take the hole
}
THIS.Array.removeat (this.Array.count-1); // Delete the last object
Return delobj;
}
#ndregion
}
}
