patterncsharpModerate
Simple binary heap in C#
Viewed 0 times
simplebinaryheap
Problem
I've written a simple binary heap in C# and I want to know if it has any problems or if I can make it better.
public enum HeapType
{
MinHeap,
MaxHeap
}
public class Heap where T : IComparable
{
List items;
public HeapType MinOrMax { get; private set; }
public T Root
{
get { return items[0]; }
}
public Heap(HeapType type)
{
items = new List();
this.MinOrMax = type;
}
public void Insert(T item)
{
items.Add(item);
int i = items.Count - 1;
bool flag = true;
if (MinOrMax == HeapType.MaxHeap)
flag = false;
while(i > 0)
{
if ((items[i].CompareTo(items[(i - 1) / 2]) > 0) ^ flag)
{
T temp = items[i];
items[i] = items[(i - 1) / 2];
items[(i - 1) / 2] = temp;
i = (i - 1) / 2;
}
else
break;
}
}
public void DeleteRoot()
{
int i = items.Count - 1;
items[0] = items[i];
items.RemoveAt(i);
i = 0;
bool flag = true;
if (MinOrMax == HeapType.MaxHeap)
flag = false;
while(true)
{
int leftInd = 2 * i + 1;
int rightInd = 2 * i + 2;
int largest = i;
if (leftInd 0) ^ flag)
largest = leftInd;
}
if (rightInd 0) ^ flag)
largest = rightInd;
}
if (largest != i)
{
T temp = items[largest];
items[largest] = items[i];
items[i] = temp;
i = largest;
}
else
break;
}
}
public T PopRoot()
{
T result = items[0];
DeleteRoot();
return result;
}
}Solution
I note that you're restricting your types
Also see https://stackoverflow.com/questions/14336416/using-icomparer-for-sorting
T to those that are IComparable, that is, those that implement CompareTo. A more general solution would allow the caller to specify their own IComparer which may be that type's CompareTo or may be something else entirely.Also see https://stackoverflow.com/questions/14336416/using-icomparer-for-sorting
Context
StackExchange Code Review Q#84530, answer score: 10
Revisions (0)
No revisions yet.