blob: d07b591dd44ca8e103b46a22b5a7e15167bd4382 (
plain)
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 + 2;
// 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;
}
public 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);
}
}
}
|