-
Notifications
You must be signed in to change notification settings - Fork 0
/
Heap.java
80 lines (69 loc) · 1.69 KB
/
Heap.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
public class Heap {
private Node[] heap;
private int size;
private int maxsize;
public int getSize() {
return size;
}
public Heap(int maxsize)
{
this.maxsize = maxsize;
this.size = 0;
heap = new Node[maxsize];
}
private void swap(int index1,int index2)
{
Node tmp;
tmp = heap[index1];
heap[index1] = heap[index2];
heap[index2] = tmp;
}
public boolean hasParent(int index){
return index > 1;
}
private void heapifyUp() {
int index = size;
while(hasParent(index)){
if(heap[index].freq < heap[index/2].freq) {
swap(index,index/2);
index = index/2;
}
else break;
}
}
private void heapifyDown(){
int i = 1;
boolean sw = false;
while (2*i<=size){
sw = false;
if (heap[2 * i].freq < heap[(2 * i) + 1].freq) {
if (heap[i].freq > heap[2 * i].freq) {
swap(i, 2*i);
i = 2 * i;
sw = true;
}
} else {
if (heap[i].freq > heap[(2 * i) + 1].freq) {
swap(i, 2*i + 1);
i = 2 * i + 1 ;
sw = true;
}
}
if(!sw) break;
}
}
public void insert(Node node)
{
if (size >= maxsize) {
return;
}
heap[++size] = node;
heapifyUp();
}
public Node pop() {
Node popped = heap[1];
heap[1] = heap[size--];
heapifyDown();
return popped;
}
}