Permalink
Find file
Fetching contributors…
Cannot retrieve contributors at this time
181 lines (152 sloc) 5.56 KB
using System;
using System.Collections.Generic;
using System.Linq;
namespace Core.Collections.Extensions.Heap
{
public static class HeapExtensions
{
/// <summary>
/// Sorts an IList of IComparable items,
/// utilizing the heap sort algorithm.
/// </summary>
public static void Heapsort(this IList<IComparable> list)
{
list.Heapify(); // list must be heapified first
for (int i = list.Count - 1; i > 0; --i) // move backward through list as i
{
Swap(list, 0, i); // swap i with 0
Sink(list, 0, i); // sink 0 up to but not including i
}
for (int i = 0; i < list.Count / 2; ++i)
{
Swap(list, i, list.Count - 1 - i);
}
}
/// <summary>
/// Heapifies the list.
/// </summary>
public static void Heapify(this IList<IComparable> list)
{
for (int k = GetParentIndex(list.Count - 1); k > -1; --k)
{
Sink(list, k, list.Count);
}
}
/// <summary>
/// Retrieves the smallest item in the heap, but does not Pop it off.
/// </summary>
public static IComparable Peek(this IList<IComparable> list)
{
return list.Count > 0 ? list[0] : null;
}
/// <summary>
/// Push the item onto the heap.
/// </summary>
public static void HeapPush(this IList<IComparable> list, IComparable item)
{
// basic idea: insert at current/last, "shift up" new item
list.Add(item);
Swim(list, list.Count - 1);
}
/// <summary>
/// Pop the smallest item off the heap.
/// </summary>
public static IComparable HeapPop(this IList<IComparable> list)
{
// basic idea: pull root aside, replace it with current/last item, "shift down" new root
if (list.Count == 0) return null;
var retval = list[0];
list[0] = list[list.Count - 1];
list.RemoveAt(list.Count - 1);
Sink(list, 0, list.Count);
return retval;
}
/// <summary>
/// Push item on the heap, then pop and return the smallest item from the heap.
/// The combined action runs more efficiently than HeapPush() followed by HeapPop().
/// </summary>
public static IComparable HeapPushPop(this IList<IComparable> list, IComparable item)
{
// TODO: Needs to be implemented.
return null;
}
public static IComparable HeapReplace(this IList<IComparable> list, IComparable item)
{
// TODO: Needs to be implemented.
return null;
}
/// <summary>
/// Calculates the parent index of the current index.
/// </summary>
private static int GetParentIndex(int index) { return (index - 1) / 2; }
/// <summary>
/// Calculates the left child index of the current index.
/// </summary>
private static int GetLeftChildIndex(int index) { return 2 * index + 1; }
/// <summary>
/// Calculates the right child index of the current index.
/// </summary>
private static int GetRightChildIndex(int index) { return 2 * index + 2; }
/// <summary>
/// Shifts item at start position upward.
/// </summary>
private static void Swim(IList<IComparable> list, int start)
{
for (int k = start, parent = GetParentIndex(k); k > -1 && Less(list, k, parent); k = parent, parent = GetParentIndex(k))
{
Swap(list, k, parent);
}
}
/// <summary>
/// Shifts item at start position downward.
/// </summary>
private static void Sink(IList<IComparable> list, int start, int count)
{
for (int k = start; k < count; )
{
int left = GetLeftChildIndex(k);
int right = GetRightChildIndex(k);
if (right < count
&& Less(list, right, left)
&& Less(list, right, k))
{
// both child nodes exist,
// the right child node < left child node,
// and right child node < k
Swap(list, k, right);
k = right;
continue;
}
if (left < count &&
Less(list, left, k))
{
// left child node < k
Swap(list, k, left);
k = left;
continue;
}
break;
}
}
/// <summary>
/// Returns true if list[i] < list[j]; otherwise returns false.
/// </summary>
private static bool Less(IList<IComparable> list, int i, int j)
{
return list[i].CompareTo(list[j]) < 0;
}
/// <summary>
/// Swaps two items in a list.
/// </summary>
private static void Swap(IList<IComparable> list, int idx1, int idx2)
{
if (idx1 >= list.Count || idx2 >= list.Count)
{
throw new IndexOutOfRangeException(string.Format("At least one of the indexes ({0}, {1}) is out of range.", idx1, idx2));
}
IComparable temp = list[idx1];
list[idx1] = list[idx2];
list[idx2] = temp;
}
}
}