Skip to content

Instantly share code, notes, and snippets.

@andrew-raphael-lukasik
Last active November 27, 2023 12:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • 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);
}
}
@BlackBlockHunter
Copy link

BlackBlockHunter commented Nov 25, 2023

This is what I got working for myself after trimming.
What's the deal with List<COMPARABLE> _comparables; and unmanaged and other stuff?

code
// src* https://gist.github.com/andrew-raphael-lukasik/b00a59509cbe8fa2b15b1949fa4f4ad2
using System.Collections.Generic;

public interface IMinHeapComparer<ITEM>
{
    int Compare(ITEM lhs, ITEM rhs);
}

public struct MinHeap<ITEM, COMPARER>
    where COMPARER : unmanaged, IMinHeapComparer<ITEM>
{
    List<ITEM> _stack;
    COMPARER _comparer;

    public int Length => _stack.Count;
    public int Count => _stack.Count;

    public MinHeap(int capacity)
    {
        this._stack = new List<ITEM>(capacity);
        this._comparer = default(COMPARER);
    }

    public void Push(ITEM item)
    {
        _stack.Add(item);
        MinHeapifyUp(_stack.Count - 1);
    }
    public ITEM Pop()
    {
        ITEM removedItem = _stack[0];
        RemoveAtSwapBack(_stack, 0);
        MinHeapifyDown(0);
        return removedItem;
    }

    public ITEM Peek() => _stack[0];
    public void Clear() => _stack.Clear();

    void MinHeapifyUp(int childIndex)
    {
        if (childIndex == 0) return;
        int parentIndex = (childIndex - 1) / 2;
        ITEM childVal = _stack[childIndex];
        ITEM parentVal = _stack[parentIndex];
        if (_comparer.Compare(childVal, 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
            && _comparer.Compare(_stack[leftChildIndex], _stack[smallestItemIndex]) < 0)
        {
            smallestItemIndex = leftChildIndex;
        }
        if (
            rightChildIndex <= this._stack.Count - 1
            && _comparer.Compare(_stack[rightChildIndex], _stack[smallestItemIndex]) < 0)
        {
            smallestItemIndex = rightChildIndex;
        }
        if (smallestItemIndex != index)
        {
            // swap the parent with the smallest of the child items
            ITEM temp = _stack[index];
            _stack[index] = _stack[smallestItemIndex];
            _stack[smallestItemIndex] = temp;
            MinHeapifyDown(smallestItemIndex);
        }
    }
    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