# Heap Rank

#### Posted on October 1, 2013

##### Last updated on November 6, 2013

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.

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:

I test the code with a test case:

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.

Markdown SHA1: 37b1fb00ccb165d74eb0759143cbda3033e53e22