dataStructures/Heap.java at master · UndefinedBehaviour/dataStructures · GitHub

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
importjava.util.List;
importjava.util.ArrayList;

publicclassHeap<TextendsComparable<T>> {

privatestaticintINITIAL_SIZE_DEFAULT = 32;

privateArrayList<T> backingArray;
privateintnumberOfItems;

Heap(intinitialSize) {
backingArray = newArrayList<T>(initialSize);
	}

Heap() {
backingArray = newArrayList<T>(INITIAL_SIZE_DEFAULT);
	}

publicvoidpush(Titem) {
backingArray.set(numberOfItems++, item);
bubbleUp();
	}

publicTpop() {
Ttmp = backingArray.get(0);
remove();
returntmp;
	}

publicvoidremove() {
backingArray.set(0, backingArray.get(numberOfItems--));
bubbleDown();
	}

publicTpeek() {
returnbackingArray.get(0);
	}

publicvoidreplace(Titem) {
backingArray.set(0, item);
bubbleDown();
	}

publicbooleanisEmpty() {
returnnumberOfItems == 0;
	}

publicstatic <C> voidheapify(C[] array) {

	}

privatevoidbubbleDown() {
intitemIndex = 0;
intleftChildIndex = 1;
intrightChildIndex = 2;

while(leftChildIndex < numberOfItems) {
intsmallerChildIndex = leftChildIndex;
if (rightChildIndex < numberOfItems) smallerChildIndex = backingArray.get(rightChildIndex).compareTo(backingArray.get(leftChildIndex)) > 0 ? rightChildIndex : leftChildIndex;
if (backingArray.get(itemIndex).compareTo(backingArray.get(smallerChildIndex)) < 0) {
swapItems(smallerChildIndex, itemIndex);
itemIndex = smallerChildIndex;
leftChildIndex = (itemIndex << 1) + 1;
rightChildIndex = leftChildIndex + 1;
 } elsereturn;
 }
	}

privatevoidbubbleUp() {
intitemIndex = numberOfItems - 1;
intparentIndex = itemIndex - 1 >> 1;

while(parentIndex >= 0)
if (backingArray.get(itemIndex).compareTo(backingArray.get(parentIndex)) > 0) {
swapItems(parentIndex, itemIndex);
itemIndex = parentIndex;
parentIndex = itemIndex - 1 >> 1;
 } elsereturn;
	}

privatevoidswapItems(inta, intb) {
Ttmp = backingArray.get(a);
backingArray.set(a, backingArray.get(b));
backingArray.set(b, tmp);
	}
}
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
importjava.util.List;
importjava.util.ArrayList;

publicclassHeap<TextendsComparable<T>> {

privatestaticintINITIAL_SIZE_DEFAULT = 32;

privateArrayList<T> backingArray;
privateintnumberOfItems;

Heap(intinitialSize) {
backingArray = newArrayList<T>(initialSize);
	}

Heap() {
backingArray = newArrayList<T>(INITIAL_SIZE_DEFAULT);
	}

publicvoidpush(Titem) {
backingArray.set(numberOfItems++, item);
bubbleUp();
	}

publicTpop() {
Ttmp = backingArray.get(0);
remove();
returntmp;
	}

publicvoidremove() {
backingArray.set(0, backingArray.get(numberOfItems--));
bubbleDown();
	}

publicTpeek() {
returnbackingArray.get(0);
	}

publicvoidreplace(Titem) {
backingArray.set(0, item);
bubbleDown();
	}

publicbooleanisEmpty() {
returnnumberOfItems == 0;
	}

publicstatic <C> voidheapify(C[] array) {

	}

privatevoidbubbleDown() {
intitemIndex = 0;
intleftChildIndex = 1;
intrightChildIndex = 2;

while(leftChildIndex < numberOfItems) {
intsmallerChildIndex = leftChildIndex;
if (rightChildIndex < numberOfItems) smallerChildIndex = backingArray.get(rightChildIndex).compareTo(backingArray.get(leftChildIndex)) > 0 ? rightChildIndex : leftChildIndex;
if (backingArray.get(itemIndex).compareTo(backingArray.get(smallerChildIndex)) < 0) {
swapItems(smallerChildIndex, itemIndex);
itemIndex = smallerChildIndex;
leftChildIndex = (itemIndex << 1) + 1;
rightChildIndex = leftChildIndex + 1;
 } elsereturn;
 }
	}

privatevoidbubbleUp() {
intitemIndex = numberOfItems - 1;
intparentIndex = itemIndex - 1 >> 1;

while(parentIndex >= 0)
if (backingArray.get(itemIndex).compareTo(backingArray.get(parentIndex)) > 0) {
swapItems(parentIndex, itemIndex);
itemIndex = parentIndex;
parentIndex = itemIndex - 1 >> 1;
 } elsereturn;
	}

privatevoidswapItems(inta, intb) {
Ttmp = backingArray.get(a);
backingArray.set(a, backingArray.get(b));
backingArray.set(b, tmp);
	}
}
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
importjava.util.List;
importjava.util.ArrayList;

publicclassHeap<TextendsComparable<T>> {

privatestaticintINITIAL_SIZE_DEFAULT = 32;

privateArrayList<T> backingArray;
privateintnumberOfItems;

Heap(intinitialSize) {
backingArray = newArrayList<T>(initialSize);
	}

Heap() {
backingArray = newArrayList<T>(INITIAL_SIZE_DEFAULT);
	}

publicvoidpush(Titem) {
backingArray.set(numberOfItems++, item);
bubbleUp();
	}

publicTpop() {
Ttmp = backingArray.get(0);
remove();
returntmp;
	}

publicvoidremove() {
backingArray.set(0, backingArray.get(numberOfItems--));
bubbleDown();
	}

publicTpeek() {
returnbackingArray.get(0);
	}

publicvoidreplace(Titem) {
backingArray.set(0, item);
bubbleDown();
	}

publicbooleanisEmpty() {
returnnumberOfItems == 0;
	}

publicstatic <C> voidheapify(C[] array) {

	}

privatevoidbubbleDown() {
intitemIndex = 0;
intleftChildIndex = 1;
intrightChildIndex = 2;

while(leftChildIndex < numberOfItems) {
intsmallerChildIndex = leftChildIndex;
if (rightChildIndex < numberOfItems) smallerChildIndex = backingArray.get(rightChildIndex).compareTo(backingArray.get(leftChildIndex)) > 0 ? rightChildIndex : leftChildIndex;
if (backingArray.get(itemIndex).compareTo(backingArray.get(smallerChildIndex)) < 0) {
swapItems(smallerChildIndex, itemIndex);
itemIndex = smallerChildIndex;
leftChildIndex = (itemIndex << 1) + 1;
rightChildIndex = leftChildIndex + 1;
 } elsereturn;
 }
	}

privatevoidbubbleUp() {
intitemIndex = numberOfItems - 1;
intparentIndex = itemIndex - 1 >> 1;

while(parentIndex >= 0)
if (backingArray.get(itemIndex).compareTo(backingArray.get(parentIndex)) > 0) {
swapItems(parentIndex, itemIndex);
itemIndex = parentIndex;
parentIndex = itemIndex - 1 >> 1;
 } elsereturn;
	}

privatevoidswapItems(inta, intb) {
Ttmp = backingArray.get(a);
backingArray.set(a, backingArray.get(b));
backingArray.set(b, tmp);
	}
}
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
importjava.util.List;
importjava.util.ArrayList;

publicclassHeap<TextendsComparable<T>> {

privatestaticintINITIAL_SIZE_DEFAULT = 32;

privateArrayList<T> backingArray;
privateintnumberOfItems;

Heap(intinitialSize) {
backingArray = newArrayList<T>(initialSize);
	}

Heap() {
backingArray = newArrayList<T>(INITIAL_SIZE_DEFAULT);
	}

publicvoidpush(Titem) {
backingArray.set(numberOfItems++, item);
bubbleUp();
	}

publicTpop() {
Ttmp = backingArray.get(0);
remove();
returntmp;
	}

publicvoidremove() {
backingArray.set(0, backingArray.get(numberOfItems--));
bubbleDown();
	}

publicTpeek() {
returnbackingArray.get(0);
	}

publicvoidreplace(Titem) {
backingArray.set(0, item);
bubbleDown();
	}

publicbooleanisEmpty() {
returnnumberOfItems == 0;
	}

publicstatic <C> voidheapify(C[] array) {

	}

privatevoidbubbleDown() {
intitemIndex = 0;
intleftChildIndex = 1;
intrightChildIndex = 2;

while(leftChildIndex < numberOfItems) {
intsmallerChildIndex = leftChildIndex;
if (rightChildIndex < numberOfItems) smallerChildIndex = backingArray.get(rightChildIndex).compareTo(backingArray.get(leftChildIndex)) > 0 ? rightChildIndex : leftChildIndex;
if (backingArray.get(itemIndex).compareTo(backingArray.get(smallerChildIndex)) < 0) {
swapItems(smallerChildIndex, itemIndex);
itemIndex = smallerChildIndex;
leftChildIndex = (itemIndex << 1) + 1;
rightChildIndex = leftChildIndex + 1;
 } elsereturn;
 }
	}

privatevoidbubbleUp() {
intitemIndex = numberOfItems - 1;
intparentIndex = itemIndex - 1 >> 1;

while(parentIndex >= 0)
if (backingArray.get(itemIndex).compareTo(backingArray.get(parentIndex)) > 0) {
swapItems(parentIndex, itemIndex);
itemIndex = parentIndex;
parentIndex = itemIndex - 1 >> 1;
 } elsereturn;
	}

privatevoidswapItems(inta, intb) {
Ttmp = backingArray.get(a);
backingArray.set(a, backingArray.get(b));
backingArray.set(b, tmp);
	}
}
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
importjava.util.List;
importjava.util.ArrayList;

publicclassHeap<TextendsComparable<T>> {

privatestaticintINITIAL_SIZE_DEFAULT = 32;

privateArrayList<T> backingArray;
privateintnumberOfItems;

Heap(intinitialSize) {
backingArray = newArrayList<T>(initialSize);
	}

Heap() {
backingArray = newArrayList<T>(INITIAL_SIZE_DEFAULT);
	}

publicvoidpush(Titem) {
backingArray.set(numberOfItems++, item);
bubbleUp();
	}

publicTpop() {
Ttmp = backingArray.get(0);
remove();
returntmp;
	}

publicvoidremove() {
backingArray.set(0, backingArray.get(numberOfItems--));
bubbleDown();
	}

publicTpeek() {
returnbackingArray.get(0);
	}

publicvoidreplace(Titem) {
backingArray.set(0, item);
bubbleDown();
	}

publicbooleanisEmpty() {
returnnumberOfItems == 0;
	}

publicstatic <C> voidheapify(C[] array) {

	}

privatevoidbubbleDown() {
intitemIndex = 0;
intleftChildIndex = 1;
intrightChildIndex = 2;

while(leftChildIndex < numberOfItems) {
intsmallerChildIndex = leftChildIndex;
if (rightChildIndex < numberOfItems) smallerChildIndex = backingArray.get(rightChildIndex).compareTo(backingArray.get(leftChildIndex)) > 0 ? rightChildIndex : leftChildIndex;
if (backingArray.get(itemIndex).compareTo(backingArray.get(smallerChildIndex)) < 0) {
swapItems(smallerChildIndex, itemIndex);
itemIndex = smallerChildIndex;
leftChildIndex = (itemIndex << 1) + 1;
rightChildIndex = leftChildIndex + 1;
 } elsereturn;
 }
	}

privatevoidbubbleUp() {
intitemIndex = numberOfItems - 1;
intparentIndex = itemIndex - 1 >> 1;

while(parentIndex >= 0)
if (backingArray.get(itemIndex).compareTo(backingArray.get(parentIndex)) > 0) {
swapItems(parentIndex, itemIndex);
itemIndex = parentIndex;
parentIndex = itemIndex - 1 >> 1;
 } elsereturn;
	}

privatevoidswapItems(inta, intb) {
Ttmp = backingArray.get(a);
backingArray.set(a, backingArray.get(b));
backingArray.set(b, tmp);
	}
}
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
importjava.util.List;
importjava.util.ArrayList;

publicclassHeap<TextendsComparable<T>> {

privatestaticintINITIAL_SIZE_DEFAULT = 32;

privateArrayList<T> backingArray;
privateintnumberOfItems;

Heap(intinitialSize) {
backingArray = newArrayList<T>(initialSize);
	}

Heap() {
backingArray = newArrayList<T>(INITIAL_SIZE_DEFAULT);
	}

publicvoidpush(Titem) {
backingArray.set(numberOfItems++, item);
bubbleUp();
	}

publicTpop() {
Ttmp = backingArray.get(0);
remove();
returntmp;
	}

publicvoidremove() {
backingArray.set(0, backingArray.get(numberOfItems--));
bubbleDown();
	}

publicTpeek() {
returnbackingArray.get(0);
	}

publicvoidreplace(Titem) {
backingArray.set(0, item);
bubbleDown();
	}

publicbooleanisEmpty() {
returnnumberOfItems == 0;
	}

publicstatic <C> voidheapify(C[] array) {

	}

privatevoidbubbleDown() {
intitemIndex = 0;
intleftChildIndex = 1;
intrightChildIndex = 2;

while(leftChildIndex < numberOfItems) {
intsmallerChildIndex = leftChildIndex;
if (rightChildIndex < numberOfItems) smallerChildIndex = backingArray.get(rightChildIndex).compareTo(backingArray.get(leftChildIndex)) > 0 ? rightChildIndex : leftChildIndex;
if (backingArray.get(itemIndex).compareTo(backingArray.get(smallerChildIndex)) < 0) {
swapItems(smallerChildIndex, itemIndex);
itemIndex = smallerChildIndex;
leftChildIndex = (itemIndex << 1) + 1;
rightChildIndex = leftChildIndex + 1;
 } elsereturn;
 }
	}

privatevoidbubbleUp() {
intitemIndex = numberOfItems - 1;
intparentIndex = itemIndex - 1 >> 1;

while(parentIndex >= 0)
if (backingArray.get(itemIndex).compareTo(backingArray.get(parentIndex)) > 0) {
swapItems(parentIndex, itemIndex);
itemIndex = parentIndex;
parentIndex = itemIndex - 1 >> 1;
 } elsereturn;
	}

privatevoidswapItems(inta, intb) {
Ttmp = backingArray.get(a);
backingArray.set(a, backingArray.get(b));
backingArray.set(b, tmp);
	}
}
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
importjava.util.List;
importjava.util.ArrayList;

publicclassHeap<TextendsComparable<T>> {

privatestaticintINITIAL_SIZE_DEFAULT = 32;

privateArrayList<T> backingArray;
privateintnumberOfItems;

Heap(intinitialSize) {
backingArray = newArrayList<T>(initialSize);
	}

Heap() {
backingArray = newArrayList<T>(INITIAL_SIZE_DEFAULT);
	}

publicvoidpush(Titem) {
backingArray.set(numberOfItems++, item);
bubbleUp();
	}

publicTpop() {
Ttmp = backingArray.get(0);
remove();
returntmp;
	}

publicvoidremove() {
backingArray.set(0, backingArray.get(numberOfItems--));
bubbleDown();
	}

publicTpeek() {
returnbackingArray.get(0);
	}

publicvoidreplace(Titem) {
backingArray.set(0, item);
bubbleDown();
	}

publicbooleanisEmpty() {
returnnumberOfItems == 0;
	}

publicstatic <C> voidheapify(C[] array) {

	}

privatevoidbubbleDown() {
intitemIndex = 0;
intleftChildIndex = 1;
intrightChildIndex = 2;

while(leftChildIndex < numberOfItems) {
intsmallerChildIndex = leftChildIndex;
if (rightChildIndex < numberOfItems) smallerChildIndex = backingArray.get(rightChildIndex).compareTo(backingArray.get(leftChildIndex)) > 0 ? rightChildIndex : leftChildIndex;
if (backingArray.get(itemIndex).compareTo(backingArray.get(smallerChildIndex)) < 0) {
swapItems(smallerChildIndex, itemIndex);
itemIndex = smallerChildIndex;
leftChildIndex = (itemIndex << 1) + 1;
rightChildIndex = leftChildIndex + 1;
 } elsereturn;
 }
	}

privatevoidbubbleUp() {
intitemIndex = numberOfItems - 1;
intparentIndex = itemIndex - 1 >> 1;

while(parentIndex >= 0)
if (backingArray.get(itemIndex).compareTo(backingArray.get(parentIndex)) > 0) {
swapItems(parentIndex, itemIndex);
itemIndex = parentIndex;
parentIndex = itemIndex - 1 >> 1;
 } elsereturn;
	}

privatevoidswapItems(inta, intb) {
Ttmp = backingArray.get(a);
backingArray.set(a, backingArray.get(b));
backingArray.set(b, tmp);
	}
}
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
importjava.util.List;
importjava.util.ArrayList;

publicclassHeap<TextendsComparable<T>> {

privatestaticintINITIAL_SIZE_DEFAULT = 32;

privateArrayList<T> backingArray;
privateintnumberOfItems;

Heap(intinitialSize) {
backingArray = newArrayList<T>(initialSize);
	}

Heap() {
backingArray = newArrayList<T>(INITIAL_SIZE_DEFAULT);
	}

publicvoidpush(Titem) {
backingArray.set(numberOfItems++, item);
bubbleUp();
	}

publicTpop() {
Ttmp = backingArray.get(0);
remove();
returntmp;
	}

publicvoidremove() {
backingArray.set(0, backingArray.get(numberOfItems--));
bubbleDown();
	}

publicTpeek() {
returnbackingArray.get(0);
	}

publicvoidreplace(Titem) {
backingArray.set(0, item);
bubbleDown();
	}

publicbooleanisEmpty() {
returnnumberOfItems == 0;
	}

publicstatic <C> voidheapify(C[] array) {

	}

privatevoidbubbleDown() {
intitemIndex = 0;
intleftChildIndex = 1;
intrightChildIndex = 2;

while(leftChildIndex < numberOfItems) {
intsmallerChildIndex = leftChildIndex;
if (rightChildIndex < numberOfItems) smallerChildIndex = backingArray.get(rightChildIndex).compareTo(backingArray.get(leftChildIndex)) > 0 ? rightChildIndex : leftChildIndex;
if (backingArray.get(itemIndex).compareTo(backingArray.get(smallerChildIndex)) < 0) {
swapItems(smallerChildIndex, itemIndex);
itemIndex = smallerChildIndex;
leftChildIndex = (itemIndex << 1) + 1;
rightChildIndex = leftChildIndex + 1;
 } elsereturn;
 }
	}

privatevoidbubbleUp() {
intitemIndex = numberOfItems - 1;
intparentIndex = itemIndex - 1 >> 1;

while(parentIndex >= 0)
if (backingArray.get(itemIndex).compareTo(backingArray.get(parentIndex)) > 0) {
swapItems(parentIndex, itemIndex);
itemIndex = parentIndex;
parentIndex = itemIndex - 1 >> 1;
 } elsereturn;
	}

privatevoidswapItems(inta, intb) {
Ttmp = backingArray.get(a);
backingArray.set(a, backingArray.get(b));
backingArray.set(b, tmp);
	}
}