Heap.cs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

using System;
using Interfaces;

namespace PriorityQueue
{
    public class Heap<T, U> where T : INode<U> where U : IComparable<U>
    {
        public T[] Array { get; set; }
        protected int HeapSize { get; set; } = -1;
        protected bool IsMin { get; set; }

        public Heap(int size = 20, bool isMin = false)
            : this(new T[size], isMin) { }

        public Heap(T[] array, bool isMin = false)
        {
            Array = array;
            IsMin = isMin;
        }


        // get node's parent
        protected int Parent(int index) =>
            (index - 1) / 2;

        // get node's left child
        protected int Left(int index) =>
            2 * index + 1;

        // get node's right child
        protected int Right(int index) =>
            2 * index + 1;

        // swap two indexies
        protected virtual void Swap(int that, int other)
        {
            // swap in heap
            T temp = Array[that];
            Array[that] = Array[other];
            Array[other] = temp;
        }

        protected bool MoreSignificant(T that, T other) =>
            that.CompareTo(other) * (IsMin ? -1 : 1) > 0;

        // build local heap
        protected void Heapify(int index)
        {
            int sig = index;

            if (Left(index) <= HeapSize && MoreSignificant(Array[Left(index)], Array[sig]))
                sig = Left(index);

            if (Right(index) <= HeapSize && MoreSignificant(Array[Right(index)], Array[sig]))
                sig = Right(index);

            if (sig != index)
            {
                Swap(index, sig);
                Heapify(sig);
            }
        }

        // build local heap for each node
        protected void BuildHeap()
        {
            for (int i = HeapSize / 2; i >= 0; i--)
                Heapify(i);
        }
    }
}