Chapter 10: Heap Algorithm from Elements of Programming Interviews

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);
  }