Wednesday, February 4, 2009
Keeping things in (partial) order, 2nd part
In the previous post I have discussed a typical case in which the use of a heap structure is very useful, presenting some code that allows to build and manage a heap structure on-top of a vector.
To complete the discussion this time I’m posting the C# code that implements a “clean” heap data structure.
// Base - The toolbox of the non-project-specific things.
// Copyright (C) 2007-2009 Andrea Esuli
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
//
// Andrea Esuli ( a n d r e a _ at _ e s u l i . i t )
using System;
using System.Collections.Generic;
namespace Esuli.Base
{
public class Heap<T>
{
private T[] items;
private int count;
private IComparer<T> comparer;
public Heap(int initialCapacity, IComparer<T> comparer)
{
if(initialCapacity == 0)
initialCapacity = 1;
items = new T[initialCapacity];
this.comparer = comparer;
}
public void Push(T item)
{
if(items.Length == count)
{
int resize = 2 * items.Length;
T[] resizedItems = new T[resize];
Array.Copy(items, 0, resizedItems, 0, items.Length);
items = resizedItems;
}
int i = count;
while(i>0) {
int parent = (i - 1) / 2;
if(comparer.Compare(item, items[parent]) < 0)
{
items[i] = items[parent];
i = parent;
}
else
break;
}
items[i] = item;
++count;
}
public T Pop()
{
if(count == 0)
return default(T);
T poppedItem = items[0];
--count;
T item = items[count];
items[count] = default(T);
int i = 0;
while(true)
{
int twoi = i * 2;
int left = twoi + 1;
if(left >= count)
break;
else
{
int right = twoi + 2;
int child = (right >= count || comparer.Compare(items[left], items[right]) < 0) ? left : right;
if(comparer.Compare(item, items[child]) > 0)
{
items[i] = items[child];
i = child;
}
else
break;
}
}
items[i] = item;
return poppedItem;
}
public T Peek()
{
if(count > 0)
return items[0];
else
return default(T);
}
public int Count
{
get
{
return count;
}
}
public virtual void Clear()
{
for(int i = 0; i < count; ++i)
items[i] = default(T);
count = 0;
}
}
}
Add comment
Fill out the form below to add your own comments