-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHeapInArray.java
More file actions
111 lines (95 loc) · 2.66 KB
/
HeapInArray.java
File metadata and controls
111 lines (95 loc) · 2.66 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
package heap;
import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.Scanner;
/**
* @author Sesh Venugopal. New Jersey. 2013
*/
class Heap4<T extends Comparable<T>> {
private ArrayList<T> items;
public Heap4() {
items = new ArrayList<T>();
}
private void siftUp() {
int k = items.size() - 1;
while (k > 0) {
int p = (k-1)/2;
T item = items.get(k);
T parent = items.get(p);
if (item.compareTo(parent) > 0) {
// swap
items.set(k, parent);
items.set(p, item);
// move up one level
k = p;
} else {
break;
}
}
}
public void insert(T item) {
items.add(item);
siftUp();
}
private void siftDown() {
int k = 0;
int l = 2*k+1;
while (l < items.size()) {
int max=l, r=l+1;
if (r < items.size()) { // there is a right child
if (items.get(r).compareTo(items.get(l)) > 0) {
max++;
}
}
if (items.get(k).compareTo(items.get(max)) < 0) {
// switch
T temp = items.get(k);
items.set(k, items.get(max));
items.set(max, temp);
k = max;
l = 2*k+1;
} else {
break;
}
}
}
public T delete()
throws NoSuchElementException {
if (items.size() == 0) {
throw new NoSuchElementException();
}
if (items.size() == 1) {
return items.remove(0);
}
T hold = items.get(0);
items.set(0, items.remove(items.size()-1));
siftDown();
return hold;
}
public int size() {
return items.size();
}
public boolean isEmpty() {
return items.isEmpty();
}
public String toString() {
return items.toString();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Heap4<Integer> hp = new Heap4<Integer>();
Scanner sc = new Scanner(System.in);
System.out.print("Enter next int, 'done' to stop: ");
String line = sc.next();
while (!line.equals("done")) {
hp.insert(Integer.parseInt(line));
System.out.println(hp);
System.out.print("Enter next int, 'done' to stop: ");
line = sc.next();
}
while (!hp.isEmpty()) {
int max = hp.delete();
System.out.println(max + " " + hp);
}
}
}