Witam, czy mógłby ktoś powiedzieć czy dobrze zaimplementowałem kopiec? Będzie on sortował elementy pewnej klasy, której priorytet będzie szacowany przez użycie zmiennej do której dostęp będzie możliwy poprzez getter wymuszany do implementacji przez interfejs IHeapValuable.
using System;
public class Heap<T> where T : IHeapValuable
{
private T[] arr;
private int heapSize;
private int GetLeftChildIndex(int parentIndex) { return 2 * parentIndex; }
private int GetRightChildIndes(int parentIndex) { return 2 * parentIndex + 1; }
private int GetParentIndex(int childInex) { return childInex / 2; }
public Heap(int maxHeapSize)
{
arr = new T[maxHeapSize];
}
private void Swap(int firstElement, int secondElement)
{
T tmp = arr[firstElement];
arr[firstElement] = arr[secondElement];
arr[secondElement] = tmp;
}
public void BuildHeap()
{
for (int i = heapSize / 2; i >= 1; i--)
MaxHeapify(i);
}
private void MaxHeapify(int index)
{
int left = GetLeftChildIndex(index);
int right = GetRightChildIndes(index);
int max;
if (left < heapSize && arr[index].GetValue < arr[left].GetValue)
max = left;
else
max = index;
if (right <= heapSize && arr[max].GetValue < arr[right].GetValue)
max = right;
if (max != index)
{
Swap(index, max);
index = max;
MaxHeapify(index);
}
}
public T GetItemWithBiggestPriority()
{
T max = arr[0];
arr[0] = arr[heapSize];
heapSize--;
MaxHeapify(0);
return max;
}
public void InsertItem(T item)
{
heapSize++;
int i = heapSize;
arr[i] = item;
while(i > 1 && item.GetValue > arr[GetParentIndex(i)].GetValue)
{
Swap(i, GetParentIndex(i));
i = GetParentIndex(i);
}
}
public void InsertItem_m(T item)
{
heapSize++;
int i = heapSize;
while (i > 1 && item.GetValue > arr[GetParentIndex(i)].GetValue)
{
Swap(i, GetParentIndex(i));
i = GetParentIndex(i);
}
arr[i] = item;
}
public void HeapSort()
{
BuildHeap();
for (int i = heapSize - 1; i >= 2; i--)
{
Swap(0, i);
heapSize--;
MaxHeapify(0);
}
}
}
public interface IHeapValuable
{
int GetValue { get; set; }
}