Last active
November 27, 2023 12:09
-
-
Save andrew-raphael-lukasik/b00a59509cbe8fa2b15b1949fa4f4ad2 to your computer and use it in GitHub Desktop.
original `Unity.Colllections` version: https://gist.github.com/andrew-raphael-lukasik/bc05310efcb1bcb2875a376494414f36
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// src* https://gist.github.com/andrew-raphael-lukasik/b00a59509cbe8fa2b15b1949fa4f4ad2 | |
using System.Collections.Generic; | |
public struct MinHeap <T> | |
where T : System.IComparable<T> | |
{ | |
List<T> _stack; | |
public int Length => _stack.Count; | |
public int Count => _stack.Count; | |
public MinHeap ( int capacity ) | |
{ | |
this._stack = new List<T>( capacity ); | |
} | |
public void Push ( T item ) | |
{ | |
_stack.Add( item ); | |
MinHeapifyUp( _stack.Count-1 ); | |
} | |
public T Pop () | |
{ | |
T removedItem = _stack[0]; | |
RemoveAtSwapBack( _stack , 0 ); | |
MinHeapifyDown( 0 ); | |
return removedItem; | |
} | |
public T Peek () => _stack[0]; | |
public void Clear () => _stack.Clear(); | |
void MinHeapifyUp ( int childIndex ) | |
{ | |
if( childIndex==0 ) return; | |
int parentIndex = (childIndex-1)/2; | |
T childVal = _stack[childIndex]; | |
T parentVal = _stack[parentIndex]; | |
if( childVal.CompareTo(parentVal)<0 ) | |
{ | |
// swap the parent and the child | |
_stack[childIndex] = parentVal; | |
_stack[parentIndex] = childVal; | |
MinHeapifyUp( parentIndex ); | |
} | |
} | |
void MinHeapifyDown ( int index ) | |
{ | |
int leftChildIndex = index * 2 + 1; | |
int rightChildIndex = index * 2 + 2; | |
int smallestItemIndex = index;// The index of the parent | |
if( | |
leftChildIndex<=this._stack.Count-1 | |
&& _stack[leftChildIndex].CompareTo(_stack[smallestItemIndex])<0 ) | |
{ | |
smallestItemIndex = leftChildIndex; | |
} | |
if( | |
rightChildIndex<=this._stack.Count-1 | |
&& _stack[rightChildIndex].CompareTo(_stack[smallestItemIndex])<0 ) | |
{ | |
smallestItemIndex = rightChildIndex; | |
} | |
if( smallestItemIndex!=index ) | |
{ | |
// swap the parent with the smallest of the child items | |
T temp = _stack[index]; | |
_stack[index] = _stack[smallestItemIndex]; | |
_stack[smallestItemIndex] = temp; | |
MinHeapifyDown( smallestItemIndex ); | |
} | |
} | |
public int Parent ( int key ) => (key-1)/2; | |
public int Left ( int key ) => 2*key + 1; | |
public int Right ( int key ) => 2*key + 2; | |
void RemoveAtSwapBack<T> ( List<T> list, int index ) | |
{ | |
int lastIndex = list.Count - 1; | |
list[index] = list[lastIndex]; | |
list.RemoveAt(lastIndex); | |
} | |
} |
What's the deal with List _comparables; and unmanaged and other stuff?
Oh that is something I leftover from the original implementation while porting it hastily; can be safely removed.
EDIT: I updated the code, removed all the unnecessary things.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This is what I got working for myself after trimming.
What's the deal with
List<COMPARABLE> _comparables;
and unmanaged and other stuff?code