using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        var words = "Now is the time for all good men to come to the aid of their country".Split(' ');

        var heap = new BinaryMinHeap<string, int>(words, w => w.Length);

​

        while (heap.Any())

        {

            var word = heap.Pop();

            Console.WriteLine(word);

        }

    }

}

​

public class Foo

{

    public int Bar;

    public string Name;

}

/// <summary>

/// <para>

/// A data structure specialized for Priority Queue implementations.

/// </para>

/// <para>

/// A Heap stays semi-sorted at all times, allowing fast retrieval of the

/// min-valued item. This is a Binary Heap, which has slower runtime in

/// theory than other variants (such as the Fibonacci Heap). However,

/// array-based heaps are simpler and often faster in practice, due to

/// factors such as memory locality and low Big-O constant factors.

/// </para>

/// <para>

/// Note: since this is a Min Heap, a LOWER priorty will be popped FIRST.

/// </para>

/// <para>

/// See https://en.wikipedia.org/wiki/Heap_(data_structure) for more.

/// </para>

/// </summary>

/// <typeparam name="TPriority">

/// The type of the priority value

/// </typeparam>

/// <typeparam name="TValue">

/// The type of the items in the collection

/// </typeparam>

/// <remarks>

/// <para>

/// This implementation stores items wrapped within a small struct, which

/// remembers the items' priority. The priority selector is used only at

/// construction time. An alternative implementation might store the items

/// directly, re-executing the priority selector as needed while sifting.

/// </para>

/// <para>

/// I chose the struct implementation based on the assumptions that the

/// structs will not greatly inflate the memory footprint, and that the

/// priority selector would be too expensive to compute more than once per

/// item. If those assumptions don't hold, then I made a bad choice.

/// </para>

/// </remarks>

public class BinaryMinHeap<TValue, TPriority>

    //where TValue : notnull // c# 8.0 constraint

    where TPriority : IComparable<TPriority>

{

    private struct Node

    {

        public TValue Item;

        public TPriority Priority;

    }

​

    private readonly List<Node> Nodes = new List<Node>();

    private readonly Dictionary<TValue, int> NodeIndexes = new Dictionary<TValue, int>();

    // TODO dotnetfiddle hack

    //private static int ParentIndex(int i) => (i - 1) / 2; // implicit floor function

    //private static int LeftChildIndex(int i) => 2 * i + 1;

    //private static int RightChildIndex(int i) => 2 * i + 2;

    private static int ParentIndex(int i) { return (i - 1) / 2; } // implicit floor function

    private static int LeftChildIndex(int i) { return 2 * i + 1; }

    private static int RightChildIndex(int i) { return 2 * i + 2; }

​

    public BinaryMinHeap(IEnumerable<TValue> items, Func<TValue, TPriority> prioritySelector)

    {

        foreach (var item in items)

        {

            NodeIndexes[item] = Nodes.Count;

            Nodes.Add(new Node

            {

                Item = item,

                Priority = prioritySelector(item),

            });

        }

​

        // Heapify. Starting from the bottom, treat each index in turn as

        // the root of its own heap, and ensure the heap property holds.

        // In fact, we can skip ahead to halfway through the array, since

        // that's where the last parent index will be.

        for (var i = ParentIndex(Nodes.Count - 1); i >= 0; i -= 1)

        {

            SiftDown(i);

        }

    }

​

    /// <summary>

    /// Is the child index within the array bounds, and does it point to a

    /// lower-priority item than the parent index?

    /// </summary>

    private bool ShouldSwap(int parentIndex, int childIndex)

    {

        // The child index is inside the array bounds,

        // and its priority is lower than the parent's

        return childIndex < Nodes.Count

            && Nodes[parentIndex].Priority.CompareTo(Nodes[childIndex].Priority) > 0;

    }

​

    /// <summary>

    /// Swap the nodes at two indexes, preserving the index map

    /// </summary>

    private void Swap(int i, int j)

    {

        var temp = Nodes[i];

​

        Nodes[i] = Nodes[j];

        NodeIndexes[Nodes[j].Item] = i;

​

        Nodes[j] = temp;

        NodeIndexes[temp.Item] = j;

    }

​

    /// <summary>

    /// Ensure that the heap rooted at this node is valid

    /// </summary>

    private void SiftDown(int parentIndex)

    {

        // While the root has at least one child

        while (parentIndex * 2 < Nodes.Count)

        {

            var leftChildIndex = LeftChildIndex(parentIndex);

            var rightChildIndex = RightChildIndex(parentIndex);

            var swapWith = parentIndex;

​

            if (ShouldSwap(swapWith, leftChildIndex))

            {

                swapWith = leftChildIndex;

            }

            if (ShouldSwap(swapWith, rightChildIndex))

            {

                swapWith = rightChildIndex;

            }

​

            if (swapWith != parentIndex)

            {

                // Swap with the lesser of the two children

                Swap(parentIndex, swapWith);

​

                // Move down the heap

                parentIndex = swapWith;

            }

            else

            {

                // The heap rooted at this index is valid. Stop.

                break;

            }

        }

    }

​

    /// <summary>

    /// Ensure that this node is in the right place in its heap

    /// </summary>

    private void SiftUp(int childIndex)

    {

        while (childIndex > 0)

        {

            var parentIndex = ParentIndex(childIndex);

            if (ShouldSwap(parentIndex, childIndex))

            {

                // This child belongs above its parent

                Swap(parentIndex, childIndex);

​

                // Keep moving up the heap

                childIndex = parentIndex;

            }

            else

            {

                // This heap is valid. Stop.

                break;

            }

        }

    }

​

    /// <summary>

    /// Returns true if the heap contains any items

    /// </summary>

    public bool Any()

    {

        return Nodes.Count > 0;

    }

​

    /// <summary>

    /// Remove the minimum item and return it

    /// </summary>

    public TValue Pop()

    {

        // Swap the first and last item

        var lastIndex = Nodes.Count - 1;

        Swap(0, lastIndex);

​

        // Remove the last item

        var minimum = Nodes[lastIndex].Item;

        Nodes.RemoveAt(lastIndex);

​

        // Re-heapify

        SiftDown(0);

​

        return minimum;

    }

​

    /// <summary>

    /// Reduce an item's priority, moving it toward the front of the queue.

    /// </summary>

    public void DecreasePriority(TValue item, TPriority newPriority)

    {

        // TODO dotnetfiddle hack

        //if (!NodeIndexes.TryGetValue(item, out var index))

        int index;

        if (!NodeIndexes.TryGetValue(item, out index))

        {

            // TODO dotnetfiddle hack

            //throw new KeyNotFoundException($"Cannot find item in heap! Item: {item}");

            throw new KeyNotFoundException(string.Format("Cannot find item in heap! Item: {0}", item));

        }

​

        var node = Nodes[index];

​

        if (!item.Equals(node.Item))

        {

            // TODO dotnetfiddle hack

            //throw new Exception($"This heap implementation sucks. Expected to find {item} at index {index}, but found {node.Item} instead.");

            throw new Exception(string.Format("This heap implementation sucks. Expected to find {0} at index {1}, but found {2} instead.", item, index, node.Item));

        }

​

        if (newPriority.CompareTo(node.Priority) > 0)

        {

            // TODO dotnetfiddle hack

            //throw new InvalidOperationException($"Cannot increase priority value! Item: {item}, old priority: {node.Priority}, new priority: {newPriority}");

            throw new InvalidOperationException(string.Format("Cannot increase priority value! Item: {0}, old priority: {1}, new priority: {2}", item, node.Priority, newPriority));

        }

​

        // Node is a struct, so we have to replace it; can't update it.

        Nodes[index] = new Node

        {

            Item = node.Item,

            Priority = newPriority,

        };

​

        SiftUp(index);

    }

}