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 \geq c\).

From this, it follows that the root of the max-heap is the largest element in the heap. A min-heap is similar in spirit, except the predicate used is \(\leq\) and the root of the min-heap is the smallest element in the min-heap.

An example of a max-heap. The largest element is at the root.

In sorted order, the elements in that heap are \([20,17,16,15,14,12,11,8,5]\).

Extracting the top element takes \(O(\operatorname{log}(n))\) time. We need to extract the top element, and then re-establish the heap property. You can find the details on Wikipedia.

1 The naive way - \(O(k\operatorname{log}(n))\)

The naive way to get the rank of element \(x\) is to simply keep extracting the maximal element from the heap until you reach the element that you desire. Since it has rank \(k\), and every time rebuilding the heap takes \(O(\operatorname{log}(n))\) time, we have a final complexity of \(O(k\operatorname{log}(n))\).

2 Optimizing 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;
}

I test the code with a test case:

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 \(5\), which is the correct rank of \(39\) in the tested array. The implementation is recursive, but can easily be changed to an iterative solution.