Slight variation of a Priority Queue

This problem exemplifies the power of a Priority Queue, as well as the advantages of having one's own implementation which you can then tweak as needed. Here it is: https://leetcode.com/problems/rank-transform-of-an-array/

1331. Rank Transform of an Array

Easy

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

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

Example 1:

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

Example 2:

Input: arr = [100,100,100]
Output: [1,1,1]
Explanation: Same elements share the same rank.

Example 3:

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

Constraints:

• 0 <= arr.length <= 105
• -109 <= arr[i] <= 109

First approach was to bubble sort the vals and the indexes and then just do a linear processing.Timed out (len = 10^5, bubble sort is n^2, hence 10^10, intractable on the leetcode system). Another approach was to use a Priority Queue. I already had an implementation of it, but needed to make a minor adjustment. The idea is to use the array index as the key in the priority queue and use the array value as the priority. Usually a dequeue operation only returns the key, so the minor change is to make it return the priority (array value) too. The value is needed to compare with the previous and decide whether or not to increment the index in the final array. Hence the total complexity is nlogn (the priority queue creation) + n, hence O(nlogn). For 10^5 input len, it does the trick. Code is below, cheers, ACC.

public class Solution
{
    public int[] ArrayRankTransform(int[] arr)
    {
        if (arr == null || arr.Length == 0) return arr;

        PriorityQueue pq = new PriorityQueue();
        for (int i = 0; i < arr.Length; i++) pq.Enqueue(i, arr[i]);

        int[] retVal = new int[arr.Length];
        long previous = Int64.MinValue;
        int count = 0;
        while (pq.Count > 0)
        {
            int current = 0;
            int index = (int)pq.Dequeue(ref current);
            if ((long)current != previous) count++;
            retVal[index] = count;
            previous = current;
        }

        return retVal;
    }
}
public class PriorityQueue
{
    public struct HeapEntry
    {
        private object item;
        private int priority;
        public HeapEntry(object item, int priority)
        {
            this.item = item;
            this.priority = priority;
        }
        public object Item
        {
            get
            {
                return item;
            }
        }
        public int Priority
        {
            get
            {
                return priority;
            }
        }
    }

    private int count;
    private int capacity;
    private HeapEntry[] heap;

    public int Count
    {
        get
        {
            return this.count;
        }
    }

    public PriorityQueue()
    {
        capacity = 100000;
        heap = new HeapEntry[capacity];
    }

    public object Dequeue(ref int priority)
    {
        object result = heap[0].Item;
        priority = heap[0].Priority;
        count--;
        trickleDown(0, heap[count]);
        return result;
    }

    public void Enqueue(object item, int priority)
    {
        count++;
        bubbleUp(count - 1, new HeapEntry(item, priority));
    }

    private void bubbleUp(int index, HeapEntry he)
    {
        int parent = (index - 1) / 2;
        // note: (index > 0) means there is a parent
        while ((index > 0) && (heap[parent].Priority > he.Priority))
        {
            heap[index] = heap[parent];
            index = parent;
            parent = (index - 1) / 2;
        }
        heap[index] = he;
    }

    private void trickleDown(int index, HeapEntry he)
    {
        int child = (index * 2) + 1;
        while (child < count)
        {
            if (((child + 1) < count) &&
                (heap[child].Priority > heap[child + 1].Priority))
            {
                child++;
            }
            heap[index] = heap[child];
            index = child;
            child = (index * 2) + 1;
        }
        bubbleUp(index, he);
    }
}