Skip to content

Instantly share code, notes, and snippets.

@andrew-raphael-lukasik
Last active November 27, 2023 12:09
Show Gist options
  • Save andrew-raphael-lukasik/b00a59509cbe8fa2b15b1949fa4f4ad2 to your computer and use it in GitHub Desktop.
Save andrew-raphael-lukasik/b00a59509cbe8fa2b15b1949fa4f4ad2 to your computer and use it in GitHub Desktop.
// 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);
}
}
@andrew-raphael-lukasik
Copy link
Author

andrew-raphael-lukasik commented Nov 27, 2023

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