tbf/SchematicDrawing/MinHeap.cs

///
/// Copyright (c) 2020 Sensus Slovensko a.s.
///
using System;
using System.Collections.Generic;

namespace SchematicDrawing
{
    public class MinHeap
    {
        GNode[] heap;   /// Minimum heap, a binary tree in form of an array
        int heapSize;   /// Heap size (not necessarily a size of the array heap[])

        /// <summary>
        /// Constructor
        /// </summary>
        public MinHeap()
        {
            heap = null;
            heapSize = 0;
        }

        /// <summary>
        /// Reset nodes and build the initial minimum heap tree.
        /// 
        /// First node on the list is the start node (mostly the main water tank),
        /// followed by 'secondaryStartNodesCount' secondary start nodes (typically
        /// tanks above scales), followed by all remaining nodes of the drawing.
        /// In this way the heap is heapified from the beginning.
        /// </summary>
        /// <param name="nodes">Graph nodes</param>
        /// <param name="secondaryStartNodesCount">Number of secondary start nodes</param>
        public void ResetAndBuild(IList<GNode> nodes, int secondaryStartNodesCount)
        {
            if (nodes == null || nodes.Count == 0) return;

            if (heapSize != nodes.Count)
            {
                heapSize = nodes.Count;
                heap = new GNode[nodes.Count];
            }

            heap[0] = nodes[0].Reset(0, 0);
            for (int i = 1; i <= secondaryStartNodesCount; i++)
            {
                heap[i] = nodes[i].Reset(i, Const.SecondaryStart);
            }
            for (int i = secondaryStartNodesCount + 1; i < nodes.Count; i++)
            {
                heap[i] = nodes[i].Reset(i, int.MaxValue);
            }
        }

        /// <summary>
        /// Returns the node with minimal distance at the top of the heap binary tree.
        /// This node is removed from the heap, replaced by the last node and the heap is 'Heapified'.
        /// </summary>
        /// <returns>Node with minimal distance</returns>
        public GNode ExtractMinNode()
        {
            GNode minNode = heap[0];
            if (--heapSize > 0)
            {
                heap[0] = heap[heapSize];   /// Swap with the last one
                heap[0].HeapIx = 0;
                heap[heapSize] = minNode;
                SiftDown(0);                /// Heapify the heap, sift down the swapped (formerly the last) item
            }
            return minNode;
        }

        /// <summary>
        /// Sift up the node in the minimum heap binary tree.
        /// Function is called when distance of a node in the graph is updated.
        /// As the distance is always decreased, the node sifts up in the tree.
        /// </summary>
        /// <param name="heapIx">Index of the node to sift up</param>
        public void SiftUp(int heapIx)
        {
            if (heapIx == 0) return;
            int parentIx = (heapIx - 1) / 2;
            if (heap[heapIx].Dist < heap[parentIx].Dist)
            {
                SwapNodes(heapIx, parentIx);
                SiftUp(parentIx);
            }
        }

        /// <summary>
        /// Sift down the node in the minimum heap binary tree.
        /// Function is called when node at the top of the tree is extracted and replaced
        /// by the last node. This last node is then sift down according to its distance.
        /// </summary>
        /// <param name="heapIx">Index of the node to sift down</param>
        void SiftDown(int heapIx)
        {
            int leftIx = 2 * heapIx + 1;
            if (leftIx < heapSize)
            {
                int minIx = heapIx;
                if (heap[leftIx].Dist < heap[minIx].Dist)
                {
                    minIx = leftIx;
                }

                int rightIx = 2 * heapIx + 2;
                if (rightIx < heapSize && heap[rightIx].Dist < heap[minIx].Dist)
                {
                    minIx = rightIx;
                }

                if (minIx != heapIx)
                {
                    SwapNodes(heapIx, minIx);
                    SiftDown(minIx);
                }
            }
        }

        /// <summary>
        /// Swap two nodes in the minimum heap binary tree.
        /// </summary>
        /// <param name="ix1">Index of the 1st node</param>
        /// <param name="ix2">Index of the 2nd node</param>
        void SwapNodes(int ix1, int ix2)
        {
            GNode swap = heap[ix1];
            heap[ix1] = heap[ix2];
            heap[ix1].HeapIx = ix1;
            heap[ix2] = swap;
            heap[ix2].HeapIx = ix2;
        }
    }
}