Heapsort

internal class Heap: StorageObjectSort {
	private object[] items;

	public int Size {
		get;
		set;
	} = 0;

	public override IEnumerable < T > Sort < T > (IComparer < T > sortFunction, IEnumerable < T > collection) {
		List < T > objectList = collection.ToList();
		Initialize(objectList.Count);
		objectList.ForEach(o = >Insert(o, sortFunction));
		objectList.Clear();

		while (Size > 0)
		objectList.Add((T) Remove(sortFunction));
		return objectList;
	}

	protected override void Insert < T > (object item, IComparer < T > sortFunction) {
		items[Size] = item;
		Size++;

		UpHeap(sortFunction);
	}

	protected override object Remove < T > (IComparer < T > sortFunction) {
		object buffer = items[0];
		items[0] = null;
		Size--;

		DownHeap(sortFunction);
		return buffer;
	}

	private void Initialize(int count) {
		items = new object[count];
	}

	private void Swap(int first, int second) {
		object buffer = items[first];
		items[first] = items[second];
		items[second] = buffer;
	}

	private int GetLeftChild(int index) {
		return GetRightChild(index) - 1;
	}

	private int GetRightChild(int index) {
		return 2 * (index + 1);
	}

	private int GetParent(int index) {
		return (index + 1) / 2 - 1;
	}

	private void UpHeap < T > (IComparer < T > sortFunction) {
		if (Size <= 1) return;

		int currentElement = Size - 1;
		int currentElementParent = GetParent(currentElement);
		while (currentElementParent >= 0 && sortFunction.Compare((T) items[currentElementParent], (T) items[currentElement]) > 0) {
			Swap(currentElement, currentElementParent);
			currentElement = currentElementParent;
			currentElementParent = GetParent(currentElement);
		}
	}

	private void DownHeap < T > (IComparer < T > sortFunction) {
		int currentIndex = 0;
		int leftChild = GetLeftChild(currentIndex);
		int rightChild = GetRightChild(currentIndex);
		while (leftChild < items.Length || rightChild < items.Length) {
			int smallerChild = GetSmallerChild < T > (sortFunction, leftChild, rightChild);
			if (smallerChild == -1) return; //There is no smaller child.
			if (items[currentIndex] == null || sortFunction.Compare((T) items[smallerChild], (T) items[currentIndex]) < 0) {
				Swap(smallerChild, currentIndex);
				currentIndex = smallerChild;
				leftChild = GetLeftChild(currentIndex);
				rightChild = GetRightChild(currentIndex);
				continue;
			}

			return;
		}
	}

	private int GetSmallerChild < T > (IComparer < T > sortFunction, int first, int second) {
		if (first >= items.Length) return second;
		else if (second >= items.Length) return first;
		else if (items[first] != null && items[second] == null) return first;
		else if (items[second] != null && items[first] == null) return second;
		else if (items[first] == null && items[second] == null) return - 1;
		return (sortFunction.Compare((T) items[first], (T) items[second]) < 0) ? first: second;
	}
}

Hinterlasse einen Kommentar

Please Login to comment
  Subscribe  
Notify of