堆
using System;using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace heap
{
/// <summary>
/// 堆排序主要使用了自底向上的方法进行了排序
/// </summary>
/// <typeparam name="T"></typeparam>
public class HEAP<T>
{
/// <summary>
/// 关联数组，数组0位置不可访问
/// </summary>
private List<T> listarray;
/// <summary>
/// 相关数据结构的比较大小的方法,比较方法的委托,要求第一个值不小于第二个的值的时候返回ture
/// </summary>
private Func<T, T, bool> comparison;
//private int heaptreeheight;
public int COUNT {
get { return listarray.Count - 1; }
}
public int TREEHEIGHT {
get { return (int)Math.Log(listarray.Count - 1, 2) + 1; }
}
private int status;
/// <summary>
/// 返回当前堆状态,0为无序堆，1为最大堆，2为最小堆
/// </summary>
public int STATUS {
get { return status; }
}
/// <summary>
/// 初始化堆
/// </summary>
/// <param name="L">关联数组</param>
/// <param name="compar">相应数据结构的比较方法</param>
public void InitHeap(List<T> L, Func<T, T, bool> compar)
{
listarray = new List<T>();
listarray.Add(L);
listarray.AddRange(L);
comparison = compar;
status = 0;
}
/// <summary>
/// 生成最大堆
/// </summary>
public void SORTHEAPMAX()
{
status = 1;
for (int i = (int)COUNT / 2; i >= 1; i--)
{
MAX_HEAPIFY(i);
}
}
/// <summary>
/// 生成最小堆
/// </summary>
public void SORTHEAPMIN()
{
status = 2;
for (int i = (int)COUNT / 2; i >= 1; i--)
{
MIN_HEAPIFY(i);
}
}
/// <summary>
/// 堆中数据元素交换位置,将值较大的元素放到上面
/// </summary>
/// <param name="start">起始位置</param>
private void MAX_HEAPIFY(int start)
{
int l = left(start);
int r = right(start);
int largest = start;
if (l <= COUNT && comparemor(listarray, listarray))
{
largest = l;
}
if (r <= COUNT && comparemor(listarray, listarray))
{
largest = r;
}
if (largest != start)
{
exchange(largest, start);
MAX_HEAPIFY(largest);
}
}
/// <summary>
/// 堆中数据元素交换位置,将值较小的元素放到上面
/// </summary>
/// <param name="start">起始位置</param>
private void MIN_HEAPIFY(int start)
{
int l = left(start);
int r = right(start);
int largest = start;
if (l <= COUNT && comparemor(listarray, listarray))
{
largest = l;
}
if (r <= COUNT && comparemor(listarray, listarray))
{
largest = r;
}
if (largest != start)
{
exchange(largest, start);
MIN_HEAPIFY(largest);
}
}
/// <summary>
/// 比较两个数据结构，并返回自定义值更大的那个
/// </summary>
/// <typeparam name="T">堆内数据结构</typeparam>
/// <param name="T1">第一个比较值</param>
/// <param name="T2">第二个比较值</param>
/// <param name="comparison">比较方法的委托,要求第一个值不小于第二个的值的时候返回ture</param>
/// <returns>当第一个值大于等于第二个值的时候返回true,当第一个值小于第二个值的时候返回false</returns>
private bool comparemor(T T1,T T2)
{
bool result = comparison(T1, T2);
if (result)
{
return true;
}
else
{
return false;
}
}
/// <summary>
/// 比较两个数据结构，并返回自定义值更小的那个
/// </summary>
/// <typeparam name="T">堆内数据结构</typeparam>
/// <param name="T1">第一个比较值</param>
/// <param name="T2">第二个比较值</param>
/// <param name="comparison">比较方法的委托,要求第一个值不小于第二个的值的时候返回ture</param>
/// <returns>返回较小值</returns>
private T compareles(T T1, T T2)
{
bool result = comparison(T1, T2);
if (result)
{
return T2;
}
else
{
return T1;
}
}
/// <summary>
/// 交换两个数据结构位置
/// </summary>
/// <param name="pos1"></param>
/// <param name="pos2"></param>
private void exchange(int pos1,int pos2)
{
T temp = listarray;
listarray = listarray;
listarray = temp;
}
//获取该节点的左孩子
private int left(int i)
{
return 2 * i;
}
//获取该节点的右孩子
private int right(int i)
{
return 2 * i + 1;
}
//获取该节点的父节点
private int parent(int i)
{
if (i != 1)
{
return (int)i / 2;
}
else
{
return 1;
}
}
/// <summary>
/// 除最后一个元素外，剩下元素最大堆或最小堆的状态下，将最后一个元素插入相应位置
/// </summary>
private void havesorttorightpos()
{
if (status == 1)//最大堆
{
int p = (int)(COUNT / 2);
int nowpos = COUNT;
bool flag = true;
while (flag)
{
if (comparemor(listarray, listarray))
{
exchange(nowpos, p);
nowpos = p;
p = (int)(nowpos / 2);
}
else
{
flag = false;
break;
}
}
}
else if (status == 2)//最小堆
{
int p = (int)(COUNT / 2);
int nowpos = COUNT;
bool flag = true;
while (flag)
{
if (comparemor(listarray,listarray))
{
exchange(nowpos, p);
nowpos = p;
p = (int)(nowpos / 2);
}
else
{
flag = false;
break;
}
}
}
else
{
}
}
/// <summary>
/// 向堆内添加元素并保持堆的原有性质
/// </summary>
/// <param name="additem">添加的对象</param>
public void add(T additem)
{
listarray.Add(additem);
havesorttorightpos();
}
/// <summary>
/// 获取堆顶
/// </summary>
/// <returns></returns>
public T gethead()
{
return listarray;
}
/// <summary>
/// 出堆
/// </summary>
/// <returns></returns>
public T outhead()
{
exchange(1, COUNT);
T temp = listarray;
listarray.Remove(listarray);
if (status == 1)//最大堆
{
MAX_HEAPIFY(1);
}
else if (status == 2)
{
MIN_HEAPIFY(1);
}
else
{
}
return temp;
}
public List<T> getall()
{
List<T> temp = new List<T>();
for (int i = 1; i <= COUNT; i++)
{
temp.Add(listarray);
}
return temp;
}
}
}
页:
[1]