C\#범 형 이 진 더미 실현
27377 단어 C#
코드 구현 방식:
using System;
using System.Collections.Generic;
namespace BinaryHeap
{
/// <summary>
///
/// </summary>
public enum Order
{
ASC = 0,
DESC = 1
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"> </typeparam>
public class BinaryHeap<T> where T : IComparable<T>
{
/// <summary>
/// The size of the heap
/// </summary>
public int Size { get; set; }
private int length;
/// <summary>
///
/// </summary>
public int Length
{
get
{
return length;
}
private set { length = value; }
}
private T[] Items { get; set; }
private Order Order = Order.ASC;
/// <summary>
/// The Cons of the heap
/// </summary>
/// <param name="size">The default size of the heap</param>
/// <param name="order">The order of the heap</param>
public BinaryHeap(int size, Order order)
{
if (size < 1)
{
throw new Exception(" 2");
}
this.Size = size;
this.Order = order;
this.Size++;
Items = new T[this.Size];
this.length = 0;
}
/*
， （ 7 ）， 17 ， 8
10 30 20 34 38 30 24 17
17 ， ， （ 8/2 = 4）， 4（ 1 ） 34， 17 34， ， ：
10 30 20 17 38 30 24 34
17 4 ， 17 （ 4/2 = 2），
2（ 1 ） 30， 17 30， ， ：
10 17 20 30 38 30 24 34
17 ， ， 2/2 = 1， 17 10， ， 17 。 17， 8 。
*/
/// <summary>
///
/// </summary>
/// <param name="item"></param>
public void Add(T item)
{
if (this.length == 0)
{
Items[1] = item;
}
else
{
int len = this.length;
if (len >= this.Size)
{
throw new Exception(" , ");
}
int endPos = len + 1;
Items[endPos] = item;
//
int parentPos = endPos / 2;
bool isContinue = true;
while (parentPos != 0 && isContinue)
{
//
if (Order == BinaryHeap.Order.ASC)
{
// -1
if (Items[endPos].CompareTo(Items[parentPos]) < 0)
{
//
Swap(ref Items[endPos], ref Items[parentPos]);
endPos = parentPos;
parentPos = endPos / 2;
}
else
{
isContinue = false;
}
}
else
{
//
if (Items[endPos].CompareTo(Items[parentPos]) > 0)
{
Swap(ref Items[endPos], ref Items[parentPos]);
endPos = parentPos;
parentPos = endPos / 2;
}
else
{
isContinue = false;
}
}
}
}
this.length++;
}
/// <summary>
///
/// </summary>
/// <returns>if the order is ASC, return the smallest one, if DESC, return the largest one.</returns>
public T Remove()
{
if (this.length == 0)
{
throw new Exception(" ");
}
//
T removedItem = Items[1];
int len = this.length;
Items[1] = Items[len]; //
//
this.length--;
//
int currentPos = 1;
int leftChildPos = currentPos * 2;
int rightChildPos = currentPos * 2 + 1;
bool isContinue = true;
while ((leftChildPos <= len || rightChildPos <= len) && isContinue)
{
// Compare the removing item to its childrens, swap each other if needed
if (Order == BinaryHeap.Order.ASC)
{
#region
if (leftChildPos <= len && rightChildPos <= len)
{
// , ( )
if (Items[leftChildPos].CompareTo(Items[rightChildPos]) < 0 && Items[currentPos].CompareTo(Items[leftChildPos]) >= 0)
{
Swap(ref Items[currentPos], ref Items[leftChildPos]);
currentPos = leftChildPos;
}
// , ( )
else if (Items[leftChildPos].CompareTo(Items[rightChildPos]) >= 0 && Items[currentPos].CompareTo(Items[rightChildPos]) >= 0)
{
Swap(ref Items[currentPos], ref Items[rightChildPos]);
currentPos = rightChildPos;
}
else
{
isContinue = false;
}
}
else if (leftChildPos <= len) //
{
if (Items[currentPos].CompareTo(Items[leftChildPos]) >= 0)
{
Swap(ref Items[currentPos], ref Items[leftChildPos]);
currentPos = leftChildPos;
}
else
{
isContinue = false;
}
}
else if (rightChildPos <= len) //
{
if (Items[currentPos].CompareTo(Items[rightChildPos]) >= 0)
{
Swap(ref Items[currentPos], ref Items[rightChildPos]);
currentPos = rightChildPos;
}
else
{
isContinue = false;
}
}
else
{
isContinue = false;
}
#endregion
leftChildPos = currentPos * 2;
rightChildPos = currentPos * 2 + 1;
}
else
{
#region
if (leftChildPos <= len && rightChildPos <= len)
{
if (Items[leftChildPos].CompareTo(Items[rightChildPos]) > 0 && Items[currentPos].CompareTo(Items[leftChildPos]) <= 0)
{
Swap(ref Items[currentPos], ref Items[leftChildPos]);
currentPos = leftChildPos;
}
else if (Items[leftChildPos].CompareTo(Items[rightChildPos]) <= 0 && Items[currentPos].CompareTo(Items[rightChildPos]) <= 0)
{
Swap(ref Items[currentPos], ref Items[rightChildPos]);
currentPos = rightChildPos;
}
else
{
isContinue = false;
}
}
else if (leftChildPos <= len)
{
if (Items[currentPos].CompareTo(Items[leftChildPos]) <= 0)
{
Swap(ref Items[currentPos], ref Items[leftChildPos]);
currentPos = leftChildPos;
}
else
{
isContinue = false;
}
}
else if (rightChildPos <= len)
{
if (Items[currentPos].CompareTo(Items[rightChildPos]) <= 0)
{
Swap(ref Items[currentPos], ref Items[rightChildPos]);
currentPos = rightChildPos;
}
else
{
isContinue = false;
}
}
else
{
isContinue = false;
}
#endregion
leftChildPos = currentPos * 2;
rightChildPos = currentPos * 2 + 1;
}
}
return removedItem;
}
/// <summary>
///
/// </summary>
/// <returns>Return the sorted heap array</returns>
public IEnumerable<T> Sort()
{
if (this.length == 0)
{
throw new Exception("The heap is empty");
}
while (this.length > 0)
{
yield return Remove();
}
}
#region Private method
/// <summary>
/// Swap each other
/// </summary>
/// <param name="t1">The first one</param>
/// <param name="t2">The second one</param>
private void Swap(ref T t1, ref T t2)
{
T temp = t1;
t1 = t2;
t2 = temp;
}
#endregion
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
WebView2를 Visual Studio 2017 Express에서 사용할 수 있을 때까지Evergreen .Net Framework SDK 4.8 VisualStudio2017에서 NuGet을 사용하기 때문에 패키지 관리 방법을 packages.config 대신 PackageReference를 사용해야...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
