如何在C#項(xiàng)目中實(shí)現(xiàn)一個(gè)最小堆的數(shù)據(jù)結(jié)構(gòu)

如何在C#項(xiàng)目中實(shí)現(xiàn)一個(gè)最小堆的數(shù)據(jù)結(jié)構(gòu)？相信很多沒(méi)有經(jīng)驗(yàn)的人對(duì)此束手無(wú)策，為此本文總結(jié)了問(wèn)題出現(xiàn)的原因和解決方法，通過(guò)這篇文章希望你能解決這個(gè)問(wèn)題。

最小堆

基本思想：堆對(duì)應(yīng)一棵完全二叉樹(shù)，且所有非葉結(jié)點(diǎn)的值均不大于(或不小于)其子女的值，根結(jié)點(diǎn)（堆頂元素）的值是最小(或最大)的，每次都取堆頂?shù)脑?，將其放在序列最后面，然后將剩余的元素重新調(diào)整為最?。ù螅┒眩来晤愅?，最終得到排序的序列。

堆排序分為大頂堆和小頂堆排序。大頂堆：堆對(duì)應(yīng)一棵完全二叉樹(shù)，且所有非葉結(jié)點(diǎn)的值均不小于其子女的值，根結(jié)點(diǎn)（堆頂元素）的值是最大的。而小頂堆正好相反，小頂堆：堆對(duì)應(yīng)一棵完全二叉樹(shù)，且所有非葉結(jié)點(diǎn)的值均不大于其子女的值，根結(jié)點(diǎn)（堆頂元素）的值是最小的。

舉個(gè)例子：

(a)大頂堆序列：（96, 83,27,38,11,09)

(b)小頂堆序列：（12，36，24，85，47，30，53，91）

實(shí)現(xiàn)堆排序需解決兩個(gè)問(wèn)題：

　　1. 如何將n 個(gè)待排序的數(shù)建成堆?

　　2. 輸出堆頂元素后，怎樣調(diào)整剩余n-1 個(gè)元素，使其成為一個(gè)新堆?

首先討論第二個(gè)問(wèn)題：輸出堆頂元素后，怎樣對(duì)剩余n-1元素重新建成堆？

調(diào)整小頂堆的方法：

　　1）設(shè)有m 個(gè)元素的堆，輸出堆頂元素后，剩下m-1 個(gè)元素。將堆底元素送入堆頂（（最后一個(gè)元素與堆頂進(jìn)行交換），堆被破壞，其原因僅是根結(jié)點(diǎn)不滿足堆的性質(zhì)。

　　2）將根結(jié)點(diǎn)與左、右子樹(shù)中較小元素的進(jìn)行交換。

　　3）若與左子樹(shù)交換：如果左子樹(shù)堆被破壞，即左子樹(shù)的根結(jié)點(diǎn)不滿足堆的性質(zhì)，則重復(fù)方法 （2）.

　　4）若與右子樹(shù)交換，如果右子樹(shù)堆被破壞，即右子樹(shù)的根結(jié)點(diǎn)不滿足堆的性質(zhì)。則重復(fù)方法 （2）.

　　5）繼續(xù)對(duì)不滿足堆性質(zhì)的子樹(shù)進(jìn)行上述交換操作，直到葉子結(jié)點(diǎn)，堆被建成。

　　稱這個(gè)自根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的調(diào)整過(guò)程為篩選。如圖：

再討論第一個(gè)問(wèn)題，如何將n 個(gè)待排序元素初始建堆？

　　建堆方法：對(duì)初始序列建堆的過(guò)程，就是一個(gè)反復(fù)進(jìn)行篩選的過(guò)程。

　　1）n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，則最后一個(gè)結(jié)點(diǎn)是第n/2個(gè)結(jié)點(diǎn)的子樹(shù)。

　　2）篩選從第n/2個(gè)結(jié)點(diǎn)為根的子樹(shù)開(kāi)始，該子樹(shù)成為堆。

　　3）之后向前依次對(duì)各結(jié)點(diǎn)為根的子樹(shù)進(jìn)行篩選，使之成為堆，直到根結(jié)點(diǎn)。

　　如圖建堆初始過(guò)程：無(wú)序序列：（49，38，65，97，76，13，27，49）

C#算法實(shí)現(xiàn)：

using System;
using System.Collections.Generic;
 
namespace StructScript
{
 /// <summary>
 /// 最小堆實(shí)現(xiàn)
 /// </summary>
 /// <typeparam name="T"></typeparam>
 public class BinaryHeap<T>
 {
  //默認(rèn)容量為6
  private const int DEFAULT_CAPACITY = 6;
  private int mCount;
  private T[] mItems;
  private Comparer<T> mComparer;
 
  public BinaryHeap() : this(DEFAULT_CAPACITY) { }
 
  public BinaryHeap(int capacity)
  {
   if (capacity < 0)
   {
    throw new IndexOutOfRangeException();
   }
   mItems = new T[capacity];
   mComparer = Comparer<T>.Default;
  }
 
  /// <summary>
  /// 增加元素到堆，并從后往前依次對(duì)各結(jié)點(diǎn)為根的子樹(shù)進(jìn)行篩選，使之成為堆，直到根結(jié)點(diǎn)
  /// </summary>
  /// <param name="value"></param>
  /// <returns></returns>
  public bool Enqueue(T value)
  {
   if (mCount == mItems.Length)
   {
    ResizeItemStore(mItems.Length * 2);
   }
 
   mItems[mCount++] = value;
   int position = BubbleUp(mCount - 1);
 
   return (position == 0);
  }
 
  /// <summary>
  /// 取出堆的最小值
  /// </summary>
  /// <returns></returns>
  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);
    // 維護(hù)堆的結(jié)構(gòu)
    BubbleDown();
   }
   if (shrink)
   {
    ShrinkStore();
   }
   return result;
  }
 
  private void ShrinkStore()
  {
   // 如果容量不足一半以上，默認(rèn)容量會(huì)下降。
   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];
  }
 
  /// <summary>
  /// 從前往后依次對(duì)各結(jié)點(diǎn)為根的子樹(shù)進(jìn)行篩選，使之成為堆，直到序列最后的節(jié)點(diǎn)
  /// </summary>
  private void BubbleDown()
  {
   int parent = 0;
   int leftChild = (parent * 2) + 1;
   while (leftChild < mCount)
   {
    // 找到子節(jié)點(diǎn)中較小的那個(gè)
    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)
    {
     // 如果子節(jié)點(diǎn)小于父節(jié)點(diǎn), 交換子節(jié)點(diǎn)和父節(jié)點(diǎn)
     T temp = mItems[parent];
     mItems[parent] = mItems[bestChild];
     mItems[bestChild] = temp;
     parent = bestChild;
     leftChild = (parent * 2) + 1;
    }
    else
    {
     break;
    }
   }
  }
 
  /// <summary>
  /// 從后往前依次對(duì)各結(jié)點(diǎn)為根的子樹(shù)進(jìn)行篩選，使之成為堆，直到根結(jié)點(diǎn)
  /// </summary>
  /// <param name="startIndex"></param>
  /// <returns></returns>
  private int BubbleUp(int startIndex)
  {
   while (startIndex > 0)
   {
    int parent = (startIndex - 1) / 2;
    //如果子節(jié)點(diǎn)小于父節(jié)點(diǎn)，交換子節(jié)點(diǎn)和父節(jié)點(diǎn)
    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;
  }
 }
}

附上，測(cè)試用例：

using System;
 
namespace StructScript
{
 public class TestBinaryHeap
 {
  static void Main(string[] args)
        {
            BinaryHeap<int> heap = new BinaryHeap<int>();
            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();
        }
 }
}

測(cè)試用例，執(zhí)行結(jié)果依次輸出1，2。

看完上述內(nèi)容，你們掌握如何在C#項(xiàng)目中實(shí)現(xiàn)一個(gè)最小堆的數(shù)據(jù)結(jié)構(gòu)的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！