-
Notifications
You must be signed in to change notification settings - Fork 1
/
BinaryHeap.java
105 lines (83 loc) · 1.84 KB
/
BinaryHeap.java
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
96
97
98
99
100
101
102
103
104
105
//import java.util.ArrayList;
public class BinaryHeap {
private static Node[] arr;
private int capacity;
private static int heap_size;
public BinaryHeap(int capacity) {
this.capacity = capacity;
heap_size = 0;
arr = new Node[capacity];
}
public int getSize() {
return heap_size;
}
public boolean isEmpty() {
return heap_size == 0;
}
public void min_heapify(int index) {
int left = left(index);
int right = right(index);
int smallest;
if (left < heap_size && arr[left].getFrequency() < arr[index].getFrequency()) {
smallest = left;
} else {
smallest = index;
}
if (right < heap_size && arr[right].getFrequency() < arr[smallest].getFrequency()) {
smallest = right;
}
if (smallest != index) {
swap(index, smallest);
min_heapify(smallest);
}
}
public static void swap(int a, int b) {
Node temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public int left(int index) {
return (2 * index) + 1;
}
public int right(int index) {
return (2 * index) + 2;
}
public int parent(int index) {
return index / 2;
}
public boolean insert(Node node) {
if (capacity == heap_size) {
return false;
}
arr[heap_size] = node;
checkAfterInsertion(heap_size++);
return true;
}
public void checkAfterInsertion(int index) {
int parent = (index - 1) / 2;
Node insertedNode = arr[index];
while (index > 0 && arr[parent].getFrequency() > insertedNode.getFrequency()) {
arr[index] = arr[parent];
index = parent;
parent = (parent - 1) / 2;
}
arr[index] = insertedNode;
}
public Node extract_min() {
if (heap_size < 1) {
System.out.println("No elements left");
return null;
} else {
Node min = arr[0];
arr[0] = arr[--heap_size];
min_heapify(0);
return min;
}
}
public Node getMin() {
if (!isEmpty()) {
return arr[0];
}
return null;
}
}