Massive Algorithms: Algorithm

Showing posts with label Algorithm. Show all posts

The Most Important Algorithms (Survey)

A* search algorithm
Graph search algorithm that finds a path from a given initial node to a given goal node. It employs a heuristic estimate that ranks each node by an estimate of the best route that goes through that node. It visits the nodes in order of this heuristic estimate. The A* algorithm is therefore an example of best-first search.

俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。

Beam Search
Beam search is a search algorithm that is an optimization of best-first search. Like best-first search, it uses a heuristic function to evaluate the promise of each node it examines. Beam search, however, only unfolds the first m most promising nodes at each depth, where m is a fixed number, the beam width.

束搜索(beam search) 方法是解决优化问题的一种启发式方法,它是在分枝定界方法基础上发展起来的,它使用启发式方法估计k 个最好的路径,仅从这k 个路径出发向下搜索,即每一层只有满意的结点会被保留,其它的结点则被永久抛弃,从而比分枝定界法能大大节省运行时间。束搜索于20 世纪70 年代中期首先被应用于人工智能领域,1976 年Lowerre 在其称为HARPY的语音识别系统中第一次使用了束搜索方法,他的目标是并行地搜索几个潜在的最优决策路径以减少回溯,并快速地获得一个解。

Binary search

Technique for finding a particular value in a linear array, by ruling out half of the data at each step.

Branch and bound
A general algorithmic method for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization.

分支定界 (branch and bound) 算法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。

Buchberger's algorithm
In computational algebraic geometry and computational commutative algebra, Buchberger's algorithm is a method of transforming a given set of generators for a polynomial ideal into a Gröbner basis with respect to some monomial order. One can view it as a generalization of the Euclidean algorithm for univariate gcd computation and of Gaussian elimination for linear systems.

Data compression
Data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an unencoded representation would use through use of specific encoding schemes.

Diffie-Hellman key exchange
Cryptographic protocol which allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher.

Dijkstra's algorithm
Algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weights.

Discrete differentiation
I.e., the formula f'(x) = (f(x+h) - f(x-h)) / 2h.

Dynamic programming
Dynamic programming is a method for reducing the runtime of algorithms exhibiting the properties of overlapping subproblems and optimal substructure, described below.

Euclidean algorithm
Algorithm to determine the greatest common divisor (gcd) of two integers. It is one of the oldest algorithms known, since it appeared in Euclid's Elements around 300 BC. The algorithm does not require factoring the two integers.

Expectation-maximization algorithm (EM-Training)
In statistical computing, an expectation-maximization (EM) algorithm is an algorithm for finding maximum likelihood estimates of parameters in probabilistic models, where the model depends on unobserved latent variables. EM alternates between performing an expectation step, which computes the expected value of the latent variables, and a maximization step, which computes the maximum likelihood estimates of the parameters given the data and setting the latent variables to their expectation.

Fast Fourier transform (FFT)
Efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. FFTs are of great importance to a wide variety of applications, from digital signal processing to solving partial differential equations to algorithms for quickly multiplying large integers.

Gradient descent
Gradient descent is an optimization algorithm that approaches a local minimum of a function by taking steps proportional to the negative of the gradient (or the approximate gradient) of the function at the current point. If instead one takes steps proportional to the gradient, one approaches a local maximum of that function; the procedure is then known as gradient ascent.

Hashing
A function for summarizing or probabilistically identifying data. Typically this means one applies a mathematical formula to the data, producing a string which is probably more or less unique to that data. The string is much shorter than the original data, but can be used to uniquely identify it.

Heaps (heap sort)
In computer science a heap is a specialized tree-based data structure. Heaps are favourite data structures for many applications: Heap sort, selection algorithms (finding the min, max or both of them, median or even any kth element in sublinear time), graph algorithms.

Karatsuba multiplication
For systems that need to multiply numbers in the range of several thousand digits, such as computer algebra systems and bignum libraries, long multiplication is too slow. These systems employ Karatsuba multiplication, which was discovered in 1962.

LLL algorithm
The Lenstra-Lenstra-Lovasz lattice reduction (LLL) algorithm is an algorithm which, given a lattice basis as input, outputs a basis with short, nearly orthogonal vectors. The LLL algorithm has found numerous applications in cryptanalysis of public-key encryption schemes: knapsack cryptosystems, RSA with particular settings, and so forth.

Maximum flow
The maximum flow problem is finding a legal flow through a flow network that is maximal. Sometimes it is defined as finding the value of such a flow. The maximum flow problem can be seen as special case of more complex network flow problems. The maximal flow is related to the cuts in a network by the Max-flow min-cut theorem. The Ford-Fulkerson algorithm computes the maximum flow in a flow network.

Merge sort
A sorting algorithm for rearranging lists (or any other data structure that can only be accessed sequentially, e.g. file streams) into a specified order.

Newton's method
Efficient algorithm for finding approximations to the zeros (or roots) of a real-valued function. Newton's method is also a well-known algorithm for finding roots of equations in one or more dimensions. It can also be used to find local maxima and local minima of functions.

Q-learning
Q-learning is a reinforcement learning technique that works by learning an action-value function that gives the expected utility of taking a given action in a given state and following a fixed policy thereafter. A strength with Q-learning is that it is able to compare the expected utility of the available actions without requiring a model of the environment.

Quadratic sieve
The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the number field sieve, NFS). It is still the fastest for integers under 110 decimal digits or so, and is considerably simpler than the number field sieve.

RANSAC
RANSAC is an abbreviation for "RANdom SAmple Consensus". It is an algorithm to estimate parameters of a mathematical model from a set of observed data which contains "outliers". A basic assumption is that the data consists of "inliers", i. e., data points which can be explained by some set of model parameters, and "outliers" which are data points that do not fit the model.

RSA
Algorithm for public-key encryption. It was the first algorithm known to be suitable for signing as well as encryption. RSA is still widely used in electronic commerce protocols, and is believed to be secure given sufficiently long keys.

Schönhage-Strassen algorithm
In mathematics, the Schönhage-Strassen algorithm is an asymptotically fast method for multiplication of large integer numbers. The run-time is O(N log(N) log(log(N))). The algorithm uses Fast Fourier Transforms in rings.

Simplex algorithm
In mathematical optimization theory, the simplex algorithm a popular technique for numerical solution of the linear programming problem. A linear programming problem consists of a collection of linear inequalities on a number of real variables and a fixed linear functional which is to be maximized (or minimized).

Singular value decomposition (SVD)
In linear algebra, SVD is an important factorization of a rectangular real or complex matrix, with several applications in signal processing and statistics, e.g., computing the pseudoinverse of a matrix (to solve the least squares problem), solving overdetermined linear systems, matrix approximation, numerical weather prediction.

Solving a system of linear equations
Systems of linear equations belong to the oldest problems in mathematics and they have many applications, such as in digital signal processing, estimation, forecasting and generally in linear programming and in the approximation of non-linear problems in numerical analysis. An efficient way to solve systems of linear equations is given by the Gauss-Jordan elimination or by the Cholesky decomposition.

Strukturtensor
In pattern recognition: Computes a measure for every pixel which tells you if this pixel is located in a homogenous region, if it belongs to an edge, or if it is a vertex.

Union-find
Given a set of elements, it is often useful to partition them into a number of separate, nonoverlapping groups. A disjoint-set data structure is a data structure that keeps track of such a partitioning. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:
Find: Determine which group a particular element is in.
Union: Combine or merge two groups into a single group.

Viterbi algorithm
Dynamic programming algorithm for finding the most likely sequence of hidden states - known as the Viterbi path - that result in a sequence of observed events, especially in the context of hidden Markov models.

Read full article from The Most Important Algorithms (Survey)

Enumerate palindromic decompositions - EPI

Enumerate palindromic decompositions PalindromePartitioning.java

public static List<List<String>> palindromePartitioning(String s) {

List<List<String>> result = new ArrayList<>();

List<String> partition = new ArrayList<>();

palindromePartitioningHelper(s, 0, partition, result);

return result;

}

private static void palindromePartitioningHelper(String s, int begin,

List<String> partition,

List<List<String>> result) {

if (begin == s.length()) {

result.add(new ArrayList<>(partition));

return;

}

for (int i = begin + 1; i <= s.length(); ++i) {

String prefix = s.substring(begin, i);

if (isPalindrome(prefix)) {

partition.add(prefix);

palindromePartitioningHelper(s, i, partition, result);

partition.remove(partition.size() - 1);

}

private static boolean isPalindrome(String s) {

for (int i = 0, j = s.length() - 1; i < j; ++i, --j) {

if (s.charAt(i) != s.charAt(j)) {

return false;

}

return true;

}

The nearest restaurant problem - EPI

The nearest restaurant problem

This algorithm solves the problem: return all keys that lies in [L,U].
Another approach: if the order is not important, we can use pre-order traverse, and check the current node range.
NearestRestaurant.java
private static <T> BinaryTree<T> findSuccessorBST(BinaryTree<T> n) {
if (n.getRight() != null) {
// Find the smallest element in n's right subtree.
n = n.getRight();
while (n.getLeft() != null) {
n = n.getLeft();
}
return n;
}

// Find the first parent which is larger than n.
while (n.getParent() != null && n.getParent().getRight() == n) {
n = n.getParent();
}
// Return nullptr means n is the largest in this BST.
return n.getParent() != null ? n.getParent() : null;
}
public static List<BinaryTree<Integer>> rangeQueryOnBST(
BinaryTree<Integer> n, Integer L, Integer U) {
List<BinaryTree<Integer>> res = new ArrayList<>();
for (BinaryTree<Integer> it = findFirstLargerEqualK(n, L); it != null
&& it.getData().compareTo(U) <= 0; it = findSuccessorBST(it)) {
res.add(it);
}
return res;
}

private static BinaryTree<Integer> findFirstLargerEqualK(
BinaryTree<Integer> r, Integer k) {
if (r == null) {
return null;
} else if (r.getData().compareTo(k) >= 0) {
// Recursively search the left subtree for first one >= k.
BinaryTree<Integer> n = findFirstLargerEqualK(r.getLeft(), k);
return n != null ? n : r;
}
// r->data < k so search the right subtree.
return findFirstLargerEqualK(r.getRight(), k);
}

POJ 2184 -- Cow Exhibition (Knapsack)

Description

The cows want to prove to the public that they are both smart and fun. In order to do this, Bessie has organized an exhibition that will be put on by the cows. She has given each of the N (1 <= N <= 100) cows a thorough interview and determined two values for each cow: the smartness Si (-1000 <= Si <= 1000) of the cow and the funness Fi (-1000 <= Fi <= 1000) of the cow.

Bessie must choose which cows she wants to bring to her exhibition. She believes that the total smartness TS of the group is the sum of the Si's and, likewise, the total funness TF of the group is the sum of the Fi's. Bessie wants to maximize the sum of TS and TF, but she also wants both of these values to be non-negative (since she must also show that the cows are well-rounded; a negative TS or TF would ruin this). Help Bessie maximize the sum of TS and TF without letting either of these values become negative.

Input

* Line 1: A single integer N, the number of cows

* Lines 2..N+1: Two space-separated integers Si and Fi, respectively the smartness and funness for each cow.

Output

* Line 1: One integer: the optimal sum of TS and TF such that both TS and TF are non-negative. If no subset of the cows has non-negative TS and non- negative TF, print 0.

Sample Input

Sample Output

http://blog.sina.com.cn/s/blog_61c7e64d0100kzul.html

牛类想要向世人证明他们聪明又幽默。经过测试，每头牛都有一个幽默度Fi和智商Si，现要求从N头牛中选择

若干头牛去参加比赛，假设这若干头牛的智商之和为sumS,幽默度之和为sumF

现要求在所有选择中，在使得sumS>=0&&sumF>=0的基础上，使得sumS+sumF最大并输出其值.

输入：

第一行： N ……N头牛 (1 <= N <= 100)

以下N行：Si Fi ……分别表示牛的智商和幽默度

输出：最大的描述中的最大值

若不存在合法的选择，输出0

PS:即选择若干对(si,fi),使得所有的s之和非负，f之和非负，且所有值之和最大

分析：

1.先求出智商s达到某个值时，幽默度能达到的最大值；2.在1基础上，选择合法项并求出最大值

难点是第一点，可转化为背包求解：

类似于0-1背包问题，s等同于花费，f等同于物品价值，为消除s出现负的影响，将原点移到100000

建设dp[s][i]为选择完前i头牛后的智商为s时可得到的最大幽默值，则状态转移方程为：

dp[s][i]=Max(dp[s-si][i-1]+fi,dp[s][i-1])

压缩空间时注意：

为防止重复相加，当前si<0时应该从左往右扫，si>0时从右往左扫

http://www.abandonzhang.com/archives/519

对于这种一个物品两个属性的问题，即使没有什么体积或者价值那么明显的情况，我们也应该考虑一下01背包是否可行.其实01背包不在于解决什么体积、价值问题，而在于这种动态规划的方法可以记录下来选择某些物品时，得到一个属性的值所对应的时刻另一个属性最优的状态.

那么显然我们就可以通过01背包来得到不同Si的值所对应能得到的Fi的最优值，然后通过枚举所有可能得到的Si值即可比较出最优解.

注意一点就是因为si[i]可能为负，所以范围要扩大一倍.

https://github.com/wuyq101/acm_test/blob/master/src/com/poj/dp/Main2184.java

n = Integer.parseInt(cin.readLine());
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(cin.readLine());
s[i] = Integer.parseInt(st.nextToken());
f[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i <= MAX; i++) {
dp[i] = -MAX;
}
dp[ZERO] = 0;
for (int i = 0; i < n; i++) {
if (s[i] < 0) {
for (int c = 0; c - s[i] <= MAX; c++) {
dp[c] = max(dp[c], dp[c - s[i]] + f[i]);
}
} else {
for (int c = MAX; c >= s[i]; c--) {
dp[c] = max(dp[c], dp[c - s[i]] + f[i]);
}
}
}
int max = 0;
for (int c = ZERO; c <= MAX; c++) {
if (dp[c] > 0 && dp[c] + c - ZERO > max) {
max = dp[c] + c - ZERO;
}
}
System.out.println(max);
}Read full article from 2184 -- Cow Exhibition

POJ 3624 -- Charm Bracelet (0/1 Knapsack)

Description

Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight W_i (1 ≤ W_i ≤ 400), a 'desirability' factor D_i (1 ≤ D_i ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).
Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

Input

* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: W_i and D_i

Output

* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints

Sample Input

Sample Output

http://blog.csdn.net/lihao21/article/details/6227445
Slyar.
Slyar:标准的01背包，动态转移方程如下。其中dp[i,j]表示的是前i个物品装入容量为j的背包里所能产生的最大价值，w[i]是第i个物品的重量，d[i]是第i个物品的价值。如果某物品超过背包容量，则该物品一定不放入背包，问题变为剩余i-1个物品装入容量为j的背包所能产生的最大价值；否则该物品装入背包，问题变为剩余i-1个物品装入容量为j-w[i]的背包所能产生的最大价值加上物品i的价值d[i]

if (w[i]>j)
dp[i,j] = dp[i-1,j]
else
dp[i,j] = max(dp[i-1,j-w[i]]+d[i],dp[i-1,j])

先上一个用二维数组求解的代码，这个代码比较容易理解。

int main()
{
int n, m;
cin >> n >> m;
/*从下标1开始存放*/
for(int i = 1; i <= n; i++) {
cin >> w[i] >> d[i];
}
/*注意，i==1或者j==1时，会用到dp边界下标为0的元素，由于已经初始化这些元素为0，保证了程序的正确运行*/
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(w[i] <= j)
dp[i][j] = max(dp[i-1][j-w[i]] + d[i], dp[i-1][j]);
else
dp[i][j] = dp[i-1][j];
}
}
cout << dp[n][m] << endl;
return 0;
}

由于OJ上memory所限，上面代码提交上去会MLE的。在纸上计算dp过程中，发觉dp设置成n行的二维数组实际上没有必要，因为在计算dp第i行时只用到dp第i-1行的数据，而且到了最后，前面n-1行都没用的。因此，完全可以用一维数组进行计算。但要注意，应从后住前计算dp，否则dp的数据会被新计算的值覆盖，导致不正确。

for(int i = 1; i <= n; i++) {
for(int j = m; j >= 1; j--) {
if(w[i] <= j)
dp[j] = max(dp[j-w[i]] + d[i], dp[j]);
else
dp[j] = dp[j];
}
}

观察二重for循环，可以发觉其实还可以继续进一步优化下

for(int i = 1; i <= n; i++) {
for(int j = m; j >= w[i]; j--) {
dp[j] = max(dp[j-w[i]] + d[i], dp[j]);
}
}

Read full article from 3624 -- Charm Bracelet

Application of Bisection Method

https://www.gjxhlan.me/2018/07/07/需要转换思路的一些题目/

有些时候，某些题目从不同的角度思考都可以得到正确的结果，但是其时间和空间复杂度却大不一样。

例如一道题可以通过递推去正向求解，但是时间复杂度可能会较高；如果这道题的某些值在一个特定的范围之内，而且我们又可以给出一个采纳或放弃这个解的线性时间的判别条件的话，不妨换个思路直接对解的值采用二分查找的策略，从而可以快速排除一些不需要枚举的状态。

Compute the integer square root
SquareRootInt.java
public static int squareRoot(int x) {
if (x <= 1) {
return x;
}

long left = 0, right = x;
while (left + 1 < right) {
long mid = left + ((right - left) / 2);
long squareM = mid * mid;
if (squareM == x) {
return (int) mid;
} else if (squareM < x) {
left = mid;
} else { // squareM > x
right = mid - 1;
}
}
if (right * right <= x) {
return (int) right;
}
return (int) left;
}

Compute the real square root

SquareRoot.java
public static double squareRoot(double x) {
// Decides the search range according to x.
double l, r;
if (compare(x, 1.0) < 0) { // x < 1.0.
l = x;
r = 1.0;
} else { // x >= 1.0.
l = 1.0;
r = x;
}

// Keeps searching if l < r.
while (compare(l, r) == -1) {
double m = l + 0.5 * (r - l);
double squareM = m * m;
if (compare(squareM, x) == 0) {
return m;
} else if (compare(squareM, x) == 1) {
r = m;
} else {
l = m;
}
}
return l;
}

// 0 means equal, -1 means smaller, and 1 means larger.
private static int compare(double a, double b) {
final double EPSILON = 0.00001;
// Uses normalization for precision problem.
double diff = (a - b) / b;
return diff < -EPSILON ? -1 : (diff > EPSILON ? 1 : 0);
}

Implement stack and queue APIs using heaps - EPI

Implement stack and queue APIs using heaps

StackQueueUsingHeapTemplate.java
private static class Compare<T> implements Comparator<Pair<Integer, T>> {
@Override
public int compare(Pair<Integer, T> o1, Pair<Integer, T> o2) {
return o2.getFirst().compareTo(o1.getFirst());
}
}

public static class Stack<T> {
private int order = 0;
private PriorityQueue<Pair<Integer, T>> H = new PriorityQueue<>(
11, new Compare<T>());

public void push(T x) {
H.add(new Pair<Integer, T>(order++, x));
}

public T pop() {
return H.remove().getSecond();
}

public T peek() {
return H.peek().getSecond();
}
}

public static class Queue<T> {
private int order = 0;
private PriorityQueue<Pair<Integer, T>> H = new PriorityQueue<>(
11, new Compare<T>());

public void enqueue(T x) {
H.add(new Pair<Integer, T>(order--, x));
}

public T dequeue() {
return H.remove().getSecond();
}

public T head() {
return H.peek().getSecond();
}
}

Build a max heap with input array

http://www.darkridge.com/~jpr5/mirror/alg/node56.html

We can build this heap by putting our data items into the array in any order and then ``heapifying'' the array. Examine the first non-leaf node in the heap-array and compare its key value against that of its greatest child. If it is greater than its greater children, proceed to the next non-leaf node and repeat this process. However, if it is not greater than its greater children then swap these elements. Before continuing to the next non-leaf node and repeating the process the algorithm must be certain that the newly demoted value is in the correct spot. Thus the process must recurse on this demoted value before it can continue with the next leaf on its way to the root. By moving up the whole heap-array in this manner all nodes will end up being greater than their children.

http://www.cise.ufl.edu/~sahni/cop3530/slides/lec242.pdf
Start at rightmost array position that has a child. Index is n/2.
http://www.geeksforgeeks.org/g-fact-85/

BUILD-HEAP(A) 
    heapsize := size(A); 
    for i := floor(heapsize/2) downto 1 
        do HEAPIFY(A, i); 
    end for 
END

What is the worst case time complexity of the above algo?
Although the worst case complexity looks like O(nLogn), upper bound of time complexity is O(n). See following links for the proof of time complexity.

http://www.cs.sfu.ca/CourseCentral/307/petra/2009/SLN_2.pdf

https://github.com/quinnliu/DataStructuresAlgorithmsDesignPatterns/blob/master/src/dataStructures/MaxHeap.java
void buildHeap() {
for (int i = (this.numberOfNodes / 2 - 1); i >= 0; i--) {
this.correctNodeIndexByShifting(i);
}
}

void correctNodeIndexByShifting(int arrayIndex) {
int changingArrayIndex = arrayIndex;
if ((changingArrayIndex < 0)
|| (changingArrayIndex >= this.numberOfNodes)) {
throw new IllegalArgumentException(
"In method shiftDown of class "
+ "MaxHeap the value: "
+ changingArrayIndex
+ " represents a node that does not exist in the current heap");
}
while (!this.isLeafNode(changingArrayIndex)) {
int childIndex = this.getLeftChildIndex(changingArrayIndex);
if ((childIndex < (this.numberOfNodes - 1))
&& (this.heap[childIndex]
.compareTo(this.heap[childIndex + 1]) < 0)) {
childIndex++; // childIndex is not at index of child with
// greater node value
}
if (this.heap[changingArrayIndex].compareTo(this.heap[childIndex]) >= 0) {
return;
}
this.swap(changingArrayIndex, childIndex);
changingArrayIndex = childIndex; // node shifted down
}
}
public void insert(E nodeValue) {
if (this.capacity <= this.numberOfNodes) {
throw new IllegalArgumentException("In method insert of class "
+ "MaxHeap the element: " + nodeValue
+ " could not be inserted because the max-heap is full");
}

int currentNodePosition = this.numberOfNodes++;
this.heap[currentNodePosition] = nodeValue;

// start at the end of most bottom right leaf node and shift up
// until the nodeValue has a parent with a greater or equal value
while ((currentNodePosition != 0)
&& (this.heap[currentNodePosition].compareTo(this.heap[this
.getParentIndex(currentNodePosition)]) > 0)) {
this.swap(currentNodePosition,
this.getParentIndex(currentNodePosition));
currentNodePosition = this.getParentIndex(currentNodePosition);
}
}
public E remove(int arrayIndex) {
int changingArrayIndex = arrayIndex;
if ((changingArrayIndex < 0)
|| (changingArrayIndex >= this.numberOfNodes)) {
throw new IllegalArgumentException("In method remove of class "
+ "MaxHeap the input node postion to be removed is invalid");
}

// if the most bottom right node is being removed there is no work to be
// done
if (changingArrayIndex == (this.numberOfNodes - 1)) {
this.numberOfNodes--;
} else {
// swap node to be removed with most bottom right node
this.swap(changingArrayIndex, --this.numberOfNodes);

// if swapped node is large, shift it up the tree
while ((changingArrayIndex > 0)
&& (this.heap[changingArrayIndex].compareTo(this.heap[this
.getParentIndex(changingArrayIndex)]) > 0)) {
this.swap(changingArrayIndex,
this.getParentIndex(changingArrayIndex));
changingArrayIndex = this.getParentIndex(changingArrayIndex);
}
if (this.numberOfNodes != 0) {
// if swapped node is small, shift it down the tree
this.correctNodeIndexByShifting(changingArrayIndex);
}
}
return this.heap[changingArrayIndex];
}
http://analgorithmaday.blogspot.com/2011/01/build-max-heap-with-input-array.html

Compute the median of online data - EPI

Compute the median of online data

OnlineMedian.java

	private static List<Double> globalResult = new ArrayList<>();

	// @include
	public static void onlineMedian(InputStream sequence) {
	// minHeap stores the larger half seen so far.
	PriorityQueue<Integer> minHeap = new PriorityQueue<>();
	// maxHeap stores the smaller half seen so far.
	PriorityQueue<Integer> maxHeap =
	new PriorityQueue<>(11, Collections.reverseOrder());

	Scanner s = new Scanner(sequence);
	while (s.hasNextInt()) {
	int x = s.nextInt();
	if (minHeap.isEmpty()) {
	// This is the very first element.
	minHeap.add(x);
	} else {
	if (x >= minHeap.peek()) {
	minHeap.add(x);
	} else {
	maxHeap.add(x);
	}
	}
	// Ensure minHeap and maxHeap have equal number of elements if
	// an even number of elements is read; otherwise, minHeap must have
	// one more element than maxHeap.
	if (minHeap.size() > maxHeap.size() + 1) {
	maxHeap.add(minHeap.remove());
	} else if (maxHeap.size() > minHeap.size()) {
	minHeap.add(maxHeap.remove());
	}

	// @exclude
	globalResult.add((minHeap.size() == maxHeap.size()
	? 0.5 * (minHeap.peek() + maxHeap.peek())
	: minHeap.peek()));
	// @include
	System.out.println(minHeap.size() == maxHeap.size()
	? 0.5 * (minHeap.peek() + maxHeap.peek())
	: minHeap.peek());
	}
	}

http://blog.csdn.net/fightforyourdream/article/details/17300465

    private static Comparator<Integer> maxHeapComparator;
    private static Comparator<Integer> minHeapComparator;
    private static PriorityQueue<Integer> maxHeap;  // 大堆里放小于中位数的元素
    private static PriorityQueue<Integer> minHeap;  // 小堆里放大于中位数的元素

    // O(logn)
 public static void addNewNumber(int randomNumber) {
            /* Note: addNewNumber maintains a condition that maxHeap.size() >= minHeap.size() */
            if (maxHeap.size() == minHeap.size()) {

  // 当小堆size与大堆相等时，中位数等于(maxHeap.top()+minHeap.top())/2
                if ((minHeap.peek() != null) && randomNumber > minHeap.peek()) {

  // 新数比中位数大，所以要放入小堆，但因为大堆的size必须大等于小堆
                    maxHeap.offer(minHeap.poll());

   // 所以要先把小堆中最小的元素移到大堆中
                    minHeap.offer(randomNumber);

   // 然后再把新数放入小堆
                } else {

   // 新数比中位数小或相等，所以放大堆
                    maxHeap.offer(randomNumber);
                }
            }
            else {

   // 这种情况必定是大堆的size比小堆多1，则中位数等于maxHeap.top()
                if(randomNumber < maxHeap.peek()){

  // 新数比中位数小或相等，所以放大堆
                    minHeap.offer(maxHeap.poll());

   // 先把大堆的最大元素转移到小堆
                    maxHeap.offer(randomNumber);

   // 然后把新数放入大堆
                }
                else {

 // 新数比中位数大，所以放小堆，因为现在大堆的size比小堆多1，所以可以直接放入小堆，无需转移
                    minHeap.offer(randomNumber);
                }
            }
    }
 // O(1)
    public static double getMedian() {
            /* maxHeap is always at least as big as minHeap. So if maxHeap is empty, then minHeap is also. */                
            if (maxHeap.isEmpty()) {
                return 0;
            }
            if (maxHeap.size() == minHeap.size()) {

  // 当大小堆size相同时，取平均
                return ((double)minHeap.peek() + (double) maxHeap.peek()) / 2;
            } else {

   // 否则大堆size比小堆多1，因此中位数就是大堆的最大值
                /* If maxHeap and minHeap are of different sizes, then maxHeap must have one extra element. Return maxHeap’s top element.*/                        
                return maxHeap.peek();
            } 
    }

Also check http://www.hawstein.com/posts/20.9.html