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
|
import java.util.ArrayList;
import java.lang.Math;
public class Heap<T extends Comparable<T>> {
private ArrayList<T> array = new ArrayList<>();
public Heap(){}
public Heap(ArrayList<T> sourceArr) {
array = sourceArr;
int pos = (int)Math.floor(array.size());
while (pos >= 0) {
siftDown(pos);
pos--;
}
// using a siftDown() algo for creating a new heap is worst case O(n)
// using a siftUp() algo would be worst case O(nlogn)
}
public T getMax() {
return array.get(0);
}
public T deleteMax() {
T toReturn = array.get(0);
array.set(0, array.get(array.size() - 1));
array.set(array.size() - 1, null);
siftDown(0);
return toReturn;
}
public void add(T value) {
array.add(value);
siftUp(array.size() - 1);
}
private void siftUp(int index) {
while (index > 0) {
int parentIndex = getParentIndex(index);
if (array.get(index).compareTo(array.get(parentIndex)) > 0) {
swap(index, parentIndex);
index = parentIndex;
} else {
return;
}
}
}
private void siftDown(int index) {
while (index * 2 <= array.size() - 1) {
int childIndex = index * 2;
if (childIndex + 1 <= array.size() - 1 && array.get(childIndex).compareTo(array.get(childIndex + 1)) < 0) {
childIndex++;
}
if (array.get(index).compareTo(array.get(childIndex)) < 0) {
swap(index, childIndex);
index = childIndex;
} else {
return;
}
}
}
private void swap(int index1, int index2) {
T temp = array.get(index1);
array.set(index1, array.get(index2));
array.set(index2, temp);
}
public static int getLeftChildIndex(int index) {
return 2 * index;
}
public static int getRightChildIndex(int index) {
return (2 * index) + 1;
}
public static int getParentIndex(int index) {
return (int)Math.floor(index / 2);
}
public String toString() {
String out = "[";
for (T elem : array) {
out += elem.toString() + ", ";
}
out += "]\n";
return out;
}
public static void main(String[] args) {
ArrayList<Integer> startArr = new ArrayList<>();
for (Integer i : new Integer[] {44, 59, 63, 10, 85, 72, 67, 12}) {
startArr.add(i);
}
Heap<Integer> heap = new Heap<>(startArr);
System.out.println(heap);
heap.add(73);
System.out.println(heap);
}
}
|
