-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMinHeap.cs
More file actions
68 lines (58 loc) · 1.54 KB
/
Copy pathMinHeap.cs
File metadata and controls
68 lines (58 loc) · 1.54 KB
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
using System;
using System.Collections.Generic;
namespace CodingProblems
{
public class MinHeap<T> where T : IComparable
{
private List<T> elements;
public int Length
{
get
{
return elements.Count;
}
}
public MinHeap()
{
elements = new List<T>();
}
public void Add(T item)
{
elements.Add(item);
Heapify();
}
public void Delete(T item)
{
int i = elements.IndexOf(item);
int last = elements.Count - 1;
elements[i] = elements[last];
elements.RemoveAt(last);
Heapify();
}
public T PopMin()
{
if (elements.Count > 0)
{
T item = elements[0];
Delete(item);
return item;
}
//relook at this - should we just throw exception?
return default(T);
}
public void Heapify()
{
for (int i = elements.Count - 1; i > 0; i--)
{
int parentPosition = (i + 1) / 2 - 1;
parentPosition = parentPosition >= 0 ? parentPosition : 0;
if (elements[parentPosition].CompareTo(elements[i]) > 1)
{
T tmp = elements[parentPosition];
elements[parentPosition] = elements[i];
elements[i] = tmp;
}
}
}
}
}