K Stars
public static ArrayList<Star> findClosestKStars(InputStream sin, int k) {
// Use maxHeap to find the closest k stars.
PriorityQueue<Star> maxHeap = new PriorityQueue<Star>();
try {
ObjectInputStream osin = new ObjectInputStream(sin);
// Record the first k stars.
while (true) {
Star s = (Star) osin.readObject();
if (maxHeap.size() == k) {
// Compare the top of heap with the incoming star.
Star farStar = maxHeap.peek();
if (s.compareTo(farStar) < 0) {
maxHeap.remove();
maxHeap.add(s);
}
} else {
maxHeap.add(s);
}
}
} catch (IOException e) {
// Do nothing, was read last element in stream
} catch (ClassNotFoundException e) {
System.out.println("ClassNotFoundException: " + e.getMessage());
}
// Store the closest k stars.
ArrayList<Star> closestStars = new ArrayList<Star>();
while (!maxHeap.isEmpty()) {
closestStars.add(maxHeap.remove());
}
return closestStars;
}
Almost sorted: at most k positions away
ApproximateSort
public static void approximateSort(InputStream sin, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
try {
ObjectInputStream osin = new ObjectInputStream(sin);
// Firstly push k elements into minHeap.
for (int i = 0; i < k; ++i) {
minHeap.add((Integer) osin.readObject());
}
// Extract the minimum one for every incoming element.
while (true) {
minHeap.add((Integer) osin.readObject());
System.out.println(minHeap.remove());
}
} catch (IOException e) {
// Do nothing, was read last element in stream
} catch (ClassNotFoundException e) {
System.out.println("ClassNotFoundException: " + e.getMessage());
}
// Extract the remaining elements in minHeap.
while (!minHeap.isEmpty()) {
System.out.println(minHeap.remove());
}
}
K elements closes to median of array
public static List<Integer> findKClosestToMedian(List<Integer> a, int k) {
// Find the element i where |a[i] - median| is k-th smallest.
final double m = findMedian(a);
nthElement(a, k - 1, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return Double.valueOf(Math.abs(a - m)).compareTo(Math.abs(b - m));
}
});
return new ArrayList<Integer>(a.subList(0, k));
}
==> How to Comparator
public static void onlineMedian(InputStream sin) {
// Min-heap stores the bigger part of the stream.
PriorityQueue<Integer> H = new PriorityQueue<Integer>();
// Max-heap stores the smaller part of the stream.
PriorityQueue<Integer> L = new PriorityQueue<Integer>(11,
new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
Scanner s = new Scanner(sin);
while (s.hasNextInt()) {
int x = s.nextInt();
if (!L.isEmpty() && x > L.peek()) {
H.add(x);
} else {
L.add(x);
}
if (H.size() > L.size() + 1) {
L.add(H.remove());
} else if (L.size() > H.size() + 1) {
H.add(L.remove());
}
if (H.size() == L.size()) {
System.out.println(0.5 * (H.peek() + L.peek()));
} else {
System.out.println((H.size() > L.size() ? H.peek() : L.peek()));
}
}
}
GeneratingABSqrt2
public static ArrayList<Num> generateFirstK(int k) {
PriorityQueue<Num> minHeap = new PriorityQueue<Num>();
ArrayList<Num> smallest = new ArrayList<Num>();
HashSet<Num> hash = new HashSet<Num>();
// Initial for 0 + 0 * sqrt(2).
minHeap.add(new Num(0, 0));
hash.add(new Num(0, 0));
while (smallest.size() < k) {
Num s = minHeap.remove();
smallest.add(s);
hash.remove(s);
// Add the next two numbers derived from s.
Num c1 = new Num(s.a + 1, s.b);
Num c2 = new Num(s.a, s.b + 1);
if (hash.add(c1)) {
minHeap.add(c1);
}
if (hash.add(c2)) {
minHeap.add(c2);
}
}
return smallest;
}
public static List<Num> generateFirstK(int k) {
List<Num> res = new ArrayList<Num>(); // stores the first-k Num.
res.add(new Num(0, 0));
int i = 0, j = 0;
for (int n = 0; n < k; ++n) {
Num x = new Num(res.get(i).a + 1, res.get(i).b);
Num y = new Num(res.get(j).a, res.get(j).b + 1);
if (x.val < y.val) {
++i;
res.add(x);
} else if (x.val > y.val) {
++j;
res.add(y);
} else { // x == y.
++i;
++j;
res.add(x);
}
}
return res;
}
Compare Kth Largest In Heap: can't modify heap
private static void compareKthLargestHeapHelper(List<Integer> maxHeap, int k,
int x, int idx, Data data) {
if (data.larger >= k || idx >= maxHeap.size() || maxHeap.get(idx) < x) {
return;
} else if (maxHeap.get(idx) == x) {
if (++data.equal >= k) {
return;
}
} else { // max_heap[idx] > x.
++data.larger;
}
compareKthLargestHeapHelper(maxHeap, k, x, (idx << 1) + 1, data);
compareKthLargestHeapHelper(maxHeap, k, x, (idx << 1) + 2, data);
}
// -1 means smaller, 0 means equal, and 1 means larger.
public static int compareKthLargestHeap(List<Integer> maxHeap, int k, int x) {
Data data = new Data();
data.larger = 0;
data.equal = 0;
compareKthLargestHeapHelper(maxHeap, k, x, 0, data);
return data.larger >= k ? 1 : (data.larger + data.equal >= k ? 0 : -1);
}
public static ArrayList<Star> findClosestKStars(InputStream sin, int k) {
// Use maxHeap to find the closest k stars.
PriorityQueue<Star> maxHeap = new PriorityQueue<Star>();
try {
ObjectInputStream osin = new ObjectInputStream(sin);
// Record the first k stars.
while (true) {
Star s = (Star) osin.readObject();
if (maxHeap.size() == k) {
// Compare the top of heap with the incoming star.
Star farStar = maxHeap.peek();
if (s.compareTo(farStar) < 0) {
maxHeap.remove();
maxHeap.add(s);
}
} else {
maxHeap.add(s);
}
}
} catch (IOException e) {
// Do nothing, was read last element in stream
} catch (ClassNotFoundException e) {
System.out.println("ClassNotFoundException: " + e.getMessage());
}
// Store the closest k stars.
ArrayList<Star> closestStars = new ArrayList<Star>();
while (!maxHeap.isEmpty()) {
closestStars.add(maxHeap.remove());
}
return closestStars;
}
Almost sorted: at most k positions away
ApproximateSort
public static void approximateSort(InputStream sin, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
try {
ObjectInputStream osin = new ObjectInputStream(sin);
// Firstly push k elements into minHeap.
for (int i = 0; i < k; ++i) {
minHeap.add((Integer) osin.readObject());
}
// Extract the minimum one for every incoming element.
while (true) {
minHeap.add((Integer) osin.readObject());
System.out.println(minHeap.remove());
}
} catch (IOException e) {
// Do nothing, was read last element in stream
} catch (ClassNotFoundException e) {
System.out.println("ClassNotFoundException: " + e.getMessage());
}
// Extract the remaining elements in minHeap.
while (!minHeap.isEmpty()) {
System.out.println(minHeap.remove());
}
}
K elements closes to median of array
public static List<Integer> findKClosestToMedian(List<Integer> a, int k) {
// Find the element i where |a[i] - median| is k-th smallest.
final double m = findMedian(a);
nthElement(a, k - 1, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return Double.valueOf(Math.abs(a - m)).compareTo(Math.abs(b - m));
}
});
return new ArrayList<Integer>(a.subList(0, k));
}
==> How to Comparator
public static void onlineMedian(InputStream sin) {
// Min-heap stores the bigger part of the stream.
PriorityQueue<Integer> H = new PriorityQueue<Integer>();
// Max-heap stores the smaller part of the stream.
PriorityQueue<Integer> L = new PriorityQueue<Integer>(11,
new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
Scanner s = new Scanner(sin);
while (s.hasNextInt()) {
int x = s.nextInt();
if (!L.isEmpty() && x > L.peek()) {
H.add(x);
} else {
L.add(x);
}
if (H.size() > L.size() + 1) {
L.add(H.remove());
} else if (L.size() > H.size() + 1) {
H.add(L.remove());
}
if (H.size() == L.size()) {
System.out.println(0.5 * (H.peek() + L.peek()));
} else {
System.out.println((H.size() > L.size() ? H.peek() : L.peek()));
}
}
}
GeneratingABSqrt2
public static ArrayList<Num> generateFirstK(int k) {
PriorityQueue<Num> minHeap = new PriorityQueue<Num>();
ArrayList<Num> smallest = new ArrayList<Num>();
HashSet<Num> hash = new HashSet<Num>();
// Initial for 0 + 0 * sqrt(2).
minHeap.add(new Num(0, 0));
hash.add(new Num(0, 0));
while (smallest.size() < k) {
Num s = minHeap.remove();
smallest.add(s);
hash.remove(s);
// Add the next two numbers derived from s.
Num c1 = new Num(s.a + 1, s.b);
Num c2 = new Num(s.a, s.b + 1);
if (hash.add(c1)) {
minHeap.add(c1);
}
if (hash.add(c2)) {
minHeap.add(c2);
}
}
return smallest;
}
public static List<Num> generateFirstK(int k) {
List<Num> res = new ArrayList<Num>(); // stores the first-k Num.
res.add(new Num(0, 0));
int i = 0, j = 0;
for (int n = 0; n < k; ++n) {
Num x = new Num(res.get(i).a + 1, res.get(i).b);
Num y = new Num(res.get(j).a, res.get(j).b + 1);
if (x.val < y.val) {
++i;
res.add(x);
} else if (x.val > y.val) {
++j;
res.add(y);
} else { // x == y.
++i;
++j;
res.add(x);
}
}
return res;
}
Compare Kth Largest In Heap: can't modify heap
private static void compareKthLargestHeapHelper(List<Integer> maxHeap, int k,
int x, int idx, Data data) {
if (data.larger >= k || idx >= maxHeap.size() || maxHeap.get(idx) < x) {
return;
} else if (maxHeap.get(idx) == x) {
if (++data.equal >= k) {
return;
}
} else { // max_heap[idx] > x.
++data.larger;
}
compareKthLargestHeapHelper(maxHeap, k, x, (idx << 1) + 1, data);
compareKthLargestHeapHelper(maxHeap, k, x, (idx << 1) + 2, data);
}
// -1 means smaller, 0 means equal, and 1 means larger.
public static int compareKthLargestHeap(List<Integer> maxHeap, int k, int x) {
Data data = new Data();
data.larger = 0;
data.equal = 0;
compareKthLargestHeapHelper(maxHeap, k, x, 0, data);
return data.larger >= k ? 1 : (data.larger + data.equal >= k ? 0 : -1);
}