<p>Given an array of integers&nbsp;<code>arr</code>, replace each element with its rank.</p>

<p>The rank represents how large the element is. The rank has the following rules:</p>

<ul>
	<li>Rank is an integer starting from 1.</li>
	<li>The larger the element, the larger the rank. If two elements are equal, their rank must be the same.</li>
	<li>Rank should be as small as possible.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [40,10,20,30]
<strong>Output:</strong> [4,1,2,3]
<strong>Explanation</strong>: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [100,100,100]
<strong>Output:</strong> [1,1,1]
<strong>Explanation</strong>: Same elements share the same rank.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> arr = [37,12,28,9,100,56,80,5,12]
<strong>Output:</strong> [5,3,4,2,8,6,7,1,3]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= arr.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>9</sup>&nbsp;&lt;= arr[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
private:
    class entry {
    public:
        int val;
        int idx;

        entry() = default;

        entry(int v, int i) {
            val = v;
            idx = i;
        }

        bool operator<(const entry& e) const {
            return val < e.val;
        }
    };

public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        int i;
        int n;
        int rank;
        int tmp;
        vector<entry> pq;

        n = arr.size();
        if (n == 0)
            return arr;

        pq.resize(n);

        for (i = 0; i < n; i = tmp) {
            tmp = i + 1;
            pq[i] = entry(arr[i], i);
            push_heap(begin(pq), begin(pq) + tmp);
        }
        sort_heap(begin(pq), begin(pq) + tmp);

        arr[pq[0].idx] = 1;
        tmp = pq[0].val;

        if (n > 1) {
            rank = 1;
            i = 1;
            for (;;) {
                entry& e = pq[i];
                int val;

                val = e.val;
                if (val > tmp)
                    ++rank;
                arr[e.idx] = rank;
                ++i;
                if (i == n)
                    break;
                tmp = val;
            }
        }

        return arr;
    }
};
35989