- using System;
- using System.Collections;
- using System.Collections.Generic;
- using UnityEditor.Localization.Plugins.XLIFF.V12;
- using UnityEditor;
- using UnityEngine;
- namespace MyCollections.Generic.Heap
- {
- public class Heap<T> where T : IheapItem<T>
- {
- //Variables
- private T[] items;
- private int currentItemCount; // Number items are currently in the heap
- //Properties
- public int Count => currentItemCount;//Gets the current number of items stored on the Heap
- //Constructor
- //Initializes the heap given maximum size
- public Heap(int maxheapSize) => items = new T[maxheapSize];
- //Adds a new item to the heap
- public void Add(T item)
- {
- item.HeapIndex = currentItemCount; //The items HeapIndex is set to the current item count.
- //This ensures the item knows its position within the array
- items[currentItemCount] = item; //The item is placed in the next available spot in the array.
- SortUp(item); //The item is sorted upwards in the heap to maintain the heap property
- currentItemCount++; //The count of items is incremented after successfully adding the item
- }
- //Removes and returns the top (or "first") item from the heap,
- //which is typically the item with the highest priority (depending on the type of heap).
- public T RemoveFirst()
- {
- T firstItem = items[0]; //The item at the top(index 0) is stored in first item to be returned later
- currentItemCount--; //The item count is decremented since we are removing an item.
- items[0] = items[currentItemCount]; //The last item in the heap is moved to the top to fill the gap left by the removed item.
- items[0].HeapIndex = 0; // The moved item's index is updated to reflect its new position at the top.
- SortDown(items[0]); //The moved item is sorted downward to maintain the heap structure.
- return firstItem; //The removed item is returned
- }
- //If an item in the heap has changed (e.g., its priority),
- //this method sorts it back up to ensure the heap maintains the correct order.
- //It assumes the item may have moved up in priority
- public void UpdateItem(T item) => SortUp(item);
- //This checks if a specific item exists in the heap by comparing the items position in the heap (item.HeapIndex)
- //to the actual object at that index
- public bool Contains(T item) => Equals(items[item.HeapIndex], item);
- //This method maintains heap order after removing an item by moving the root element downwards
- private void SortDown(T item)
- {
- while (true)
- {
- //Gets the left child index
- int childIndexLeft = item.HeapIndex * 2 + 1;
- //Gets the right child index
- int childIndexRight = item.HeapIndex * 2 + 2;
- //is initialized to track which child (if any)
- //the current node needs to be swapped with during the sorting process.
- int swapIndex = 0;
- //This checks if the current node (item) has a left child
- //if childIndexLeft is out of bounds (i.e., greater than or equal to currentItemCount),
- //the node has no children, and the method can terminate early.
- if (childIndexLeft < currentItemCount)
- {
- //Stores the child to swap
- swapIndex = childIndexLeft;
- //This checks if the current node (item) has a right child
- if (childIndexRight < currentItemCount)
- {
- //If the left child is smaller (or less preferred), the swapIndex remains as the left child
- //If the right child is smaller(or less preferred), swapIndex is updated to the right child
- if (items[childIndexLeft].CompareTo(items[childIndexRight]) < 0)
- {
- swapIndex = childIndexRight;
- }
- }
- //If the parent (item) is smaller than the child it’s being compared to,
- //a swap is performed.
- if (item.CompareTo(items[swapIndex]) < 0)
- {
- Swap(item, items[swapIndex]); //Swap performed
- }
- else
- {
- return;
- }
- }
- else
- {
- return;
- }
- }
- }
- //This is the counterpart to SortDown and is called when adding a new item or updating an item in the heap.
- //It moves the item upwards to ensure the heap order is maintained,
- //checking the item's parent and swapping them if necessary.
- private void SortUp(T item)
- {
- //The parent index is calculated using the formula for a binary heap
- int parentIndex = (item.HeapIndex - 1) / 2;
- while (true)
- {
- //Gets the parent item
- T parentItem = items[parentIndex];
- //If item is greater than parentItem (indicating the heap property is violated), a swap is needed.
- if (item.CompareTo(parentItem) > 0)
- {
- //Applies the swap
- Swap(item, parentItem);
- }
- else
- {
- break;
- }
- //After a swap, the parentIndex is recalculated based on the updated HeapIndex of the item
- parentIndex = (item.HeapIndex - 1) / 2;
- }
- }
- //This swaps two items in the heap, updating both their positions
- //in the array and their HeapIndex
- private void Swap(T itemA, T itemB)
- {
- items[itemA.HeapIndex] = itemB;
- items[itemB.HeapIndex] = itemA;
- int itemAIndex = itemA.HeapIndex;
- itemA.HeapIndex = itemB.HeapIndex;
- itemB.HeapIndex = itemAIndex;
- }
- }
- //This interface is essential because it provides the HeapIndex
- //and comparison functionality for sorting items in the heap.
- public interface IheapItem<T> : IComparable<T>
- {
- int HeapIndex { get; set; }
- }
- }