/
MaxHeap.java
133 lines (116 loc) · 3 KB
/
MaxHeap.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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
/**
* A bound Max Heap of int type elements.
* This is a binary heap with array as the underlying container.
*/
public class MaxHeap {
public static final int INF = Integer.MAX_VALUE;
private final int capacity;
private int size;
/*
* Put the elements into an array, but the logical relationship is a binary tree.
* 0 is the root;
* i's left child is 2*i + 1, right child is 2*i + 2;
* i's parent is (i-1) / 2.
*/
private final int[] elements;
public MaxHeap(int capacity) {
this.capacity = capacity;
size = 0;
elements = new int[capacity];
}
/**
* Nothing happens if heap is full.
*/
public void offer(int e) {
if (isFull()) {
// Overflowed.
return;
}
/*
* Put the new element at the end of the heap.
* Push it up until it is less than its parent.
*/
size++;
int i = size - 1;
elements[i] = e;
while (i != 0 && elements[parent(i)] < elements[i]) {
swap(i, parent(i));
i = parent(i);
}
}
public int heapSize() {
return size;
}
public int peek() {
if (isEmpty()) {
return INF;
}
return elements[0];
}
public void clear() {
size = 0;
}
public int poll() {
if (isEmpty()) {
return INF;
}
if (size == 1) {
size--;
return elements[0];
}
/*
* Root is the max value in the heap, will be removed and returned to caller.
* Push down the tree and select the max of left and right as the new parent.
*/
int root = elements[0];
elements[0] = elements[size - 1];
size--;
heapify(0);
return root;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
/*
* Heapify the sub-tree rooted with index i.
* Find the largest value among parent, left and right;
* If the parent is the largest, we are done.
* Swap parent with the largest sub-node, now parent is the largest;
* Keep heapifying the swapped sub-tree.
*/
private void heapify(int i) {
int l = left(i);
int r = right(i);
int largest = i;
if (l < size && elements[l] > elements[i]) {
largest = l;
}
if (r < size && elements[r] > elements[largest]) {
largest = r;
}
if (largest != i) {
swap(i, largest);
heapify(largest);
}
}
private void swap(int i, int j) {
if (i == j) {
return;
}
int t = elements[i];
elements[i] = elements[j];
elements[j] = t;
}
private int parent(int i) {
return (i - 1) / 2;
}
private int left(int i) {
return (i << 1) + 1;
}
private int right(int i) {
return (i << 1) + 2;
}
}