-
Notifications
You must be signed in to change notification settings - Fork 11
/
MaxHeap.cs
96 lines (78 loc) · 1.97 KB
/
MaxHeap.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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
List<int> input = new() { 1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17 };
MaxHeap maxHeap = new(input);
maxHeap.PrintHeap();
Console.WriteLine("Insert 25");
maxHeap.Insert(25);
maxHeap.PrintHeap();
Console.WriteLine("Peek " + maxHeap.Peek());
Console.WriteLine("Item removed");
maxHeap.Remove();
maxHeap.PrintHeap();
public class MaxHeap
{
List<int> heap = new();
public MaxHeap(List<int> heap)
{
this.heap = heap;
BuildHeap();
}
public void BuildHeap()
{
//Find last parent
int lastChild = heap.Count - 1;
int lastParent = (lastChild - 1) / 2;
for (int i = lastParent; i >= 0; i--)
{
Heapify(i);
}
}
//Time: O(n log(n)), Space: O(log(n))
private void Heapify(int i)
{
int max = i;
int l = 2 * i + 1; // left child = 2*i + 1
int r = 2 * i + 2; // right child = 2*i + 2
if (l < heap.Count && heap[l] > heap[max]) //Left child is larger than root
max = l;
if (r < heap.Count && heap[r] > heap[max])//Right child is larger than largest so far
max = r;
if (max != i)
{
Swap(i, max, heap);
Heapify(max);
}
}
//Time: O(n)
public void PrintHeap()
{
for (int i = 0; i < heap.Count; ++i)
Console.Write(heap[i] + " ");
Console.WriteLine();
}
//Time: O(1)
public int Peek()
{
return heap[0];
}
//Time: O(log n)
public int Remove()
{
int count = heap.Count - 1;
Swap(0, count, heap);//Swap root with last node
int removedValue = heap[count];//romoves head;
heap.RemoveAt(count);
BuildHeap();
return removedValue;
}
//Time: O(log n)
public void Insert(int value)
{
heap.Add(value);
BuildHeap();
}
private void Swap(int i, int j, List<int> array)
{
(array[j], array[i]) = (array[i], array[j]);
}
}