Study heap rank pseudo code from the blog: https://rafal.io/posts/heap-rank.html

HeapRank studyCode

Problem statement:

Given a binary max-heap with N elements, and an element x from the heap, find the rank k of x in 
the heap. The rank of the element is the element’s position after sorting in decreasing order 
all the elements from the heap; for example, the root element has rank 1. Assume x appears once in the heap.

Before diving into this problem, let’s revise what a max-heap is. The max-heap is a complete binary
tree that also satisfies the following max-heap property:

If c is a child node of p, then p ≥ c.

Brute force solution is O(klogn). But the optimized solution is to use recursive solution to find the node with 
value larger than given value. 

Optimized to O(K)

Consider the element x’s position in the max-heap. Anything smaller than x necessarily has 
higher rank than x, by definition, and hence we are not interested in these nodes. Also, 
there are k−1 elements larger than x since x has rank k.

Consider a subtree of the max-heap such that an element of the max-heap is part of the subtree 
iff it’s greater than or equal to x. This leaves x as the smallest element in the subtree. 
Consequently, the size of that subtree is k. This leads to the following algorithm:

  Find all the nodes greater than or equal to x
  The number of these nodes gives the rank of x
  
Because of the heap property, if we are exploring a node and it’s smaller than x, we no longer 
need to explore that heap branch further – all the elements there are smaller than x and 
hence of no interest.

What’s left to do is to traverse to heap in some way. Since we are bound to visit only k nodes, 
the complexity is O(k). With a standard array-based implementation of a heap, the code for this 
algorithm might look like this:


// pre: the element with value x is in the heap
public int rank(int x){
  return rankR(x,0);
}

private int rankR(int x, int curNodeIndex){
  int curNodeValue = arr[curNodeIndex];
  if(curNodeValue >= x){
    int lValue = 0;
    int rValue = 0;
    if(left(curNodeIndex) < heapSize) lValue = rankR(x,left(curNodeIndex));
    if(right(curNodeIndex) < heapSize) rValue = rankR(x,right(curNodeIndex));
    return 1 + lValue + rValue;
  }
  return 0;
}

public static void main(String[] args) {
		int[] arr = {38,203,1,45,39,10,34,90,10,2,100,1};
		MaxHeap m = new MaxHeap();
		m.initWithArray(arr);
		System.out.println(m.rank(39));
}

The code prints 55, which is the correct rank of 3939 in the tested array. The implementation is recursive,
but can easily be changed to an iterative solution.