forked from xiaoningning/java-algorithm-2010
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMinHeap.java
More file actions
120 lines (103 loc) · 3.17 KB
/
MinHeap.java
File metadata and controls
120 lines (103 loc) · 3.17 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
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
/**
* http://algs4.cs.princeton.edu/24pq/
* min heap: only keep the min at the top, parent(root) < left and right node
*/
public class MinHeap {
private int maxSize;
private int current;
private int[] heap;
public MinHeap(int max) {
maxSize = max;
heap = new int[maxSize + 1]; // min is heap[1], it easy to calculate left/right
current = 0; // current index
}
public void insert(int value) {
if (current == maxSize) {
throw new RuntimeException("Heap is full!");
}
heap[++current] = value; // start from 1
shiftUp(current);
}
public boolean isEmpty() {
return current == 0;
}
public int min() {
if (isEmpty())
throw new RuntimeException("heap is empty");
return heap[1];
}
public int removeMin() {
if (isEmpty())
throw new RuntimeException("heap is empty");
int min = heap[1];
swap(1, current);
// heap[current] = Integer.MAX_VALUE;
current--;
if(current != 0 )
shiftDown(1);
return min;
}
private void shiftUp(int k) {
// k/2 is parent, parent < left/right
while (k > 1 && heap[k / 2] > heap[k]) {
swap(k / 2, k);
k = k / 2;
}
}
private void shiftDown(int k) {
while (2 * k <= current) {
int i = 2 * k; // left child
int j = i + 1; // right child
//find the smallest of left and right
if (i < current && heap[i] > heap[j]) {
i++; // i = j
}
if (heap[k] < heap[i]) {
break;
}
swap(k, i);
k = i;
}
}
private void swap(int i, int j) {
int tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
}
// is pq[1..N] a min heap?
private boolean isMinHeap() {
return isMinHeap(1);
}
// is subtree of pq[1..N] rooted at k a min heap?
private boolean isMinHeap(int k) {
if (k > current) return true;
int left = 2 * k, right = 2 * k + 1;
if (left <= current && heap[k] > heap[left]) return false;
if (right <= current && heap[k] > heap[right]) return false;
return isMinHeap(left) && isMinHeap(right);
}
public void printHeap() {
System.out.print("heap: ");
for (int i = 1; i <= current; i++) {
System.out.print(heap[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] a = new int[]{5, 3, 4, 1, 0, 6, 7, 2};
MinHeap minHeap = new MinHeap(a.length);
for (int i = 0; i < a.length; i++) {
minHeap.insert(a[i]);
}
System.out.println(minHeap.isMinHeap());
minHeap.printHeap();
System.out.println(minHeap.removeMin());
System.out.println(minHeap.removeMin());
System.out.println(minHeap.isMinHeap());
minHeap.printHeap();
System.out.println(minHeap.removeMin());
System.out.println(minHeap.removeMin());
System.out.println(minHeap.removeMin());
minHeap.printHeap();
}
}