C#练习二叉堆算法。
namespace 算法
{
/// <summary>
/// 最大堆
/// </summary>
/// <typeparam name="T"></typeparam>
public class IndexMaxHeap<T> where T:IComparable<T>
{
/// <summary>
/// 堆空间大小
/// </summary>
private int capacity;
/// <summary>
/// 数据项
/// </summary>
private T[] items;
/// <summary>
/// 堆实际大小
/// </summary>
private int count;
/// <summary>
/// 构造方法，由用户指定开辟空间大小，注意元素从1开始
/// </summary>
/// <param name="n"></param>
public IndexMaxHeap(int n)
{
capacity = n+1;
items = new T[capacity];
count = 0;
}
/// <summary>
/// 堆实际大小
/// </summary>
/// <returns>返回堆实际大小int类型</returns>
public int size()
{
return count;
}
/// <summary>
/// 堆中是否有数据
/// </summary>
/// <returns></returns>
public bool isEmpty()
{
return count == 0;
}
/// <summary>
/// 堆中插入一个元素
/// </summary>
/// <param name="item"></param>
public void insert(T item)
{
if (count+1 > capacity)
{
throw new IndexOutOfRangeException("堆空间溢出");
}
items[++count] = item;
shiftUp(count);
}
/// <summary>
/// 出堆
/// </summary>
public T extractMax()
{
if (count <= 0)
{
throw new IndexOutOfRangeException("空数据");
}
T maxItem = items[1];
//先交换位置
swap(ref items[1], ref items[count]);
count--;
//做一次shiftdown操作
shiftDown(1);
return maxItem;
}
private void shiftDown(int n)
{
while (n*2<=count)
{
int des = 2*n;
if (2 * n + 1<=count && items[n * 2].CompareTo(items[2 * n + 1]) < 0)
{
des = 2 * n + 1;
}
if (items[n].CompareTo(items[des]) < 0)
{
swap(ref items[n], ref items[des]);
n = des;
}
else
{
break;
}
}
}
public void print()
{
for(int i = 1; i <= count; i++)
{
Console.WriteLine(items[i]);
}
}
/// <summary>
/// 将堆底元素向上提
/// </summary>
/// <param name="n"></param>
private void shiftUp(int n)
{
//只要父级元素大于它，就一直循环并交换
while (n>1 && items[n].CompareTo(items[n/2])>0)
{
int j = n / 2;
swap(ref items[n], ref items[j]);
n = j;
}
}
private void swap(ref T a,ref T b)
{
T c = a;
a = b;
b = c;
}
}
public class Test
{
public static void Main()
{
IndexMaxHeap<int> heap = new IndexMaxHeap<int>(15);
for (int i = 0; i < 10; i++)
{
Random rd = new Random();
int a = rd.Next(10, 100);
heap.insert(a);
// Console.WriteLine(a);
}
Console.WriteLine("---");
Console.WriteLine($"最大值：{heap.extractMax()}");
heap.print();
Console.WriteLine("+++++++++++++++");
HeapSort<int>(new int[5] { 3, 2, 4, 6, 7 });
Console.ReadKey();
}
/// <summary>
/// 堆排序
/// </summary>
public static T[] HeapSort<T>(T[] arr ) where T:IComparable<T>
{
IndexMaxHeap<T> a = new IndexMaxHeap<T>(100);
for(int i = 0; i < arr.Length; i++)
{
a.insert(arr[i]);
}
//从小到大
for(int i = arr.Length-1; i >=0; i--)
{
T t = a.extractMax();
arr[i] = t;
}
return arr;
}
}
public class a : IComparable<a>
{
public int CompareTo(a other)
{
throw new NotImplementedException();
}
}
}