.net core 中实现一个堆结构
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了.net core 中实现一个堆结构,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2716字,纯文字阅读大概需要4分钟。
内容图文
堆结构的内部是以数组实现,表现形式为一个完全二叉树,对应关系上,上级节点的下标始终等于直接下级节点的下标(任意一个)除2的除数,下级节点的坐标左孩子为上级坐标的位置2+1,右孩子为上级坐标的位置2+2,这个条件始终满足
如下代码就是一个简易的堆结构实现
using System;
namespace test1
{
public enum HeapType
{
Max,
Min
}
public class Heap<T> where T:IComparable<T>
{
private T[] _source;
private int _heapSize;
private HeapType _heapType;
public Heap(HeapType heapType)
{
this._heapType = heapType;
_source = new T[0];
_heapSize = 0;//堆大小为0;
}
public Heap(HeapType heapType,T[] lst)
{
this._heapType = heapType;
_source = lst;
_heapSize = lst.Length;//堆大小为0;
Heapfiy();
}
/// <summary>
/// 获取当前最前边的值
/// </summary>
public T GetTopValue
{
get
{
if (_heapSize > 0)
{
var result = _source[0];
swap(0, _heapSize-- - 1);//交换最后一个项,并调整堆大小
Heapfiy(0);
return result;
}
else
{
return default(T);
}
}
}
/// <summary>
/// 插入数据
/// </summary>
/// <param name="item"></param>
public void HeapInsert(T item)
{
if (++_heapSize > _source.Length)
{
var newlst = new T[_heapSize];
for (int i = 0; i < _source.Length; i++)
{
newlst[i] = _source[i];
}
_source = newlst;
}
_source[_heapSize-1] = item;
//与上级比较 父index= i-1/2
var currentindex = _heapSize-1;
var parrentindex = (currentindex - 1) >> 1;
while (currentindex>0)
{
switch (_heapType)
{
case HeapType.Max:
if (_source[currentindex].CompareTo(_source[parrentindex])>0)
{
swap(currentindex, parrentindex);
}
break;
case HeapType.Min:
if (_source[currentindex].CompareTo(_source[parrentindex]) < 0)
{
swap(currentindex, parrentindex);
}
break;
}
currentindex = parrentindex;
parrentindex = (currentindex - 1) >> 1;
}
}
/// <summary>
/// 某一个位置的值下移到合适的位置
/// </summary>
/// <param name="index"></param>
private void Heapfiy(int index)
{
var i = index;
switch (_heapType)
{
case HeapType.Max:
while (i * 2 + 1 < _heapSize)//有子项就一路执行,并且小于子项
{
//找到目标孩子的i
int targetchlidi = i * 2 + 1;
if (i * 2 + 2 < _heapSize)//有右孩子
{
targetchlidi = _source[i * 2 + 1].CompareTo(_source[i * 2 + 2]) > 0 ? i * 2 + 1 : i * 2 + 2;
}
if (_source[i].CompareTo(_source[targetchlidi]) < 0)
{
swap(i, targetchlidi);
i = targetchlidi;
}
else
{
break;
}
}
break;
case HeapType.Min:
while (i * 2 + 1 < _heapSize)//有子项就一路执行
{
//找到目标孩子的i
int targetchlidi = i * 2 + 1;
if (i * 2 + 2 < _heapSize)//有右孩子
{
targetchlidi = _source[i * 2 + 1].CompareTo(_source[i * 2 + 2]) < 0 ? i * 2 + 1 : i * 2 + 2;
}
if (_source[i].CompareTo(_source[targetchlidi]) > 0)
{
swap(i, targetchlidi);
i = targetchlidi;
}
else
{
break;
}
}
break;
default:
break;
}
}
/// <summary>
/// 对所有位置执行下移操作
/// </summary>
private void Heapfiy()
{
for (int i = _heapSize >> 1; i >=0; i--)
{
Heapfiy(i);
}
}
private void swap(int a, int b)
{
T r = _source[a];
_source[a] = _source[b];
_source[b] = r;
}
}
}
内容总结
以上是互联网集市为您收集整理的.net core 中实现一个堆结构全部内容,希望文章能够帮你解决.net core 中实现一个堆结构所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。