如何在C#项目中实现一个最小堆的数据结构-创新互联

如何在C#项目中实现一个最小堆的数据结构?相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。

为尼河口等地区用户提供了全套网页设计制作服务,及尼河口网站建设行业解决方案。主营业务为网站设计制作、成都网站建设、尼河口网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!

最小堆

基本思想:堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或较大)的,每次都取堆顶的元素,将其放在序列最后面,然后将剩余的元素重新调整为最小(大)堆,依次类推,最终得到排序的序列。

堆排序分为大顶堆和小顶堆排序。大顶堆:堆对应一棵完全二叉树,且所有非叶结点的值均不小于其子女的值,根结点(堆顶元素)的值是较大的。而小顶堆正好相反,小顶堆:堆对应一棵完全二叉树,且所有非叶结点的值均不大于其子女的值,根结点(堆顶元素)的值是最小的。

举个例子:

(a)大顶堆序列:(96, 83,27,38,11,09)

(b)小顶堆序列:(12,36,24,85,47,30,53,91)

如何在C#项目中实现一个最小堆的数据结构

实现堆排序需解决两个问题:

1. 如何将n 个待排序的数建成堆?

2. 输出堆顶元素后,怎样调整剩余n-1 个元素,使其成为一个新堆?

首先讨论第二个问题:输出堆顶元素后,怎样对剩余n-1元素重新建成堆?

调整小顶堆的方法:

1)设有m 个元素的堆,输出堆顶元素后,剩下m-1 个元素。将堆底元素送入堆顶((最后一个元素与堆顶进行交换),堆被破坏,其原因仅是根结点不满足堆的性质。

2)将根结点与左、右子树中较小元素的进行交换。

3)若与左子树交换:如果左子树堆被破坏,即左子树的根结点不满足堆的性质,则重复方法 (2).

4)若与右子树交换,如果右子树堆被破坏,即右子树的根结点不满足堆的性质。则重复方法 (2).

5)继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。

称这个自根结点到叶子结点的调整过程为筛选。如图:

如何在C#项目中实现一个最小堆的数据结构

再讨论第一个问题,如何将n 个待排序元素初始建堆?

建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。

1)n 个结点的完全二叉树,则最后一个结点是第n/2个结点的子树。

2)筛选从第n/2个结点为根的子树开始,该子树成为堆。

3)之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。

如图建堆初始过程:无序序列:(49,38,65,97,76,13,27,49)

如何在C#项目中实现一个最小堆的数据结构

如何在C#项目中实现一个最小堆的数据结构

C#算法实现:

using System;
using System.Collections.Generic;
 
namespace StructScript
{
 /// 
 /// 最小堆实现
 /// 
 /// 
 public class BinaryHeap
 {
  //默认容量为6
  private const int DEFAULT_CAPACITY = 6;
  private int mCount;
  private T[] mItems;
  private Comparer mComparer;
 
  public BinaryHeap() : this(DEFAULT_CAPACITY) { }
 
  public BinaryHeap(int capacity)
  {
   if (capacity < 0)
   {
    throw new IndexOutOfRangeException();
   }
   mItems = new T[capacity];
   mComparer = Comparer.Default;
  }
 
  /// 
  /// 增加元素到堆,并从后往前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点
  /// 
  /// 
  /// 
  public bool Enqueue(T value)
  {
   if (mCount == mItems.Length)
   {
    ResizeItemStore(mItems.Length * 2);
   }
 
   mItems[mCount++] = value;
   int position = BubbleUp(mCount - 1);
 
   return (position == 0);
  }
 
  /// 
  /// 取出堆的最小值
  /// 
  /// 
  public T Dequeue()
  {
   return Dequeue(true);
  }
 
  private T Dequeue(bool shrink)
  {
   if (mCount == 0)
   {
    throw new InvalidOperationException();
   }
   T result = mItems[0];
   if (mCount == 1)
   {
    mCount = 0;
    mItems[0] = default(T);
   }
   else
   {
    --mCount;
    //取序列最后的元素放在堆顶
    mItems[0] = mItems[mCount];
    mItems[mCount] = default(T);
    // 维护堆的结构
    BubbleDown();
   }
   if (shrink)
   {
    ShrinkStore();
   }
   return result;
  }
 
  private void ShrinkStore()
  {
   // 如果容量不足一半以上,默认容量会下降。
   if (mItems.Length > DEFAULT_CAPACITY && mCount < (mItems.Length >> 1))
   {
    int newSize = Math.Max(
     DEFAULT_CAPACITY, (((mCount / DEFAULT_CAPACITY) + 1) * DEFAULT_CAPACITY));
 
    ResizeItemStore(newSize);
   }
  }
 
  private void ResizeItemStore(int newSize)
  {
   if (mCount < newSize || DEFAULT_CAPACITY <= newSize)
   {
    return;
   }
 
   T[] temp = new T[newSize];
   Array.Copy(mItems, 0, temp, 0, mCount);
   mItems = temp;
  }
 
  public void Clear()
  {
   mCount = 0;
   mItems = new T[DEFAULT_CAPACITY];
  }
 
  /// 
  /// 从前往后依次对各结点为根的子树进行筛选,使之成为堆,直到序列最后的节点
  /// 
  private void BubbleDown()
  {
   int parent = 0;
   int leftChild = (parent * 2) + 1;
   while (leftChild < mCount)
   {
    // 找到子节点中较小的那个
    int rightChild = leftChild + 1;
    int bestChild = (rightChild < mCount && mComparer.Compare(mItems[rightChild], mItems[leftChild]) < 0) ?
     rightChild : leftChild;
    if (mComparer.Compare(mItems[bestChild], mItems[parent]) < 0)
    {
     // 如果子节点小于父节点, 交换子节点和父节点
     T temp = mItems[parent];
     mItems[parent] = mItems[bestChild];
     mItems[bestChild] = temp;
     parent = bestChild;
     leftChild = (parent * 2) + 1;
    }
    else
    {
     break;
    }
   }
  }
 
  /// 
  /// 从后往前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点
  /// 
  /// 
  /// 
  private int BubbleUp(int startIndex)
  {
   while (startIndex > 0)
   {
    int parent = (startIndex - 1) / 2;
    //如果子节点小于父节点,交换子节点和父节点
    if (mComparer.Compare(mItems[startIndex], mItems[parent]) < 0)
    {
     T temp = mItems[startIndex];
     mItems[startIndex] = mItems[parent];
     mItems[parent] = temp;
    }
    else
    {
     break;
    }
    startIndex = parent;
   }
   return startIndex;
  }
 }
}

附上,测试用例:

using System;
 
namespace StructScript
{
 public class TestBinaryHeap
 {
  static void Main(string[] args)
        {
            BinaryHeap heap = new BinaryHeap();
            heap.Enqueue(8);
            heap.Enqueue(2);
            heap.Enqueue(3);
            heap.Enqueue(1);
            heap.Enqueue(5);
 
            Console.WriteLine(heap.Dequeue());
            Console.WriteLine(heap.Dequeue());
 
            Console.ReadLine();
        }
 }
}

测试用例,执行结果依次输出1,2。

看完上述内容,你们掌握如何在C#项目中实现一个最小堆的数据结构的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注创新互联行业资讯频道,感谢各位的阅读!


网页名称:如何在C#项目中实现一个最小堆的数据结构-创新互联
URL链接:http://lszwz.com/article/pihis.html

其他资讯

售后响应及时

7×24小时客服热线

数据备份

更安全、更高效、更稳定

价格公道精准

项目经理精准报价不弄虚作假

合作无风险

重合同讲信誉,无效全额退款