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
72
73

using System;
using PriorityQueue.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 void Swap(int that, int other)
        {
            // swap in heap
            T temp = Array[that];
            Array[that] = Array[other];
            Array[other] = temp;
        }

        protected int CompareKey(T that, T other) =>
            that.CompareTo(other) * (IsMin ? -1 : 1);

        // build local heap
        protected void Heapify(int index)
        {
            int sig = index;
            int left = 2 * index + 1;
            int right = 2 * index + 2;

            if (left <= HeapSize && CompareKey(Array[left], Array[sig]) > 0)
                sig = left;

            if (right <= HeapSize && CompareKey(Array[right], Array[sig]) > 0)
                sig = right;

            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);
        }
    }
}