The mathematics of a priority queue sorting with big integers

This is a problem that exemplifies how to use mathematics and a priority queue to get to a fast and efficient solution. Here it is: https://leetcode.com/problems/rank-teams-by-votes/

1366. Rank Teams by Votes

Medium

In a special ranking system, each voter gives a rank from highest to lowest to all teams participated in the competition.

The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.

Given an array of strings votes which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.

Return a string of all teams sorted by the ranking system.

Example 1:

Input: votes = ["ABC","ACB","ABC","ACB","ACB"]
Output: "ACB"
Explanation: Team A was ranked first place by 5 voters. No other team was voted as first place so team A is the first team.
Team B was ranked second by 2 voters and was ranked third by 3 voters.
Team C was ranked second by 3 voters and was ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team and team B is the third.

Example 2:

Input: votes = ["WXYZ","XYZW"]
Output: "XWYZ"
Explanation: X is the winner due to tie-breaking rule. X has same votes as W for the first position but X has one vote as second position while W doesn't have any votes as second position. 

Example 3:

Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK"
Explanation: Only one voter so his votes are used for the ranking.

Example 4:

Input: votes = ["BCA","CAB","CBA","ABC","ACB","BAC"]
Output: "ABC"
Explanation: 
Team A was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team B was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team C was ranked first by 2 voters, second by 2 voters and third by 2 voters.
There is a tie and we rank teams ascending by their IDs.

Example 5:

Input: votes = ["M","M","M","M"]
Output: "M"
Explanation: Only team M in the competition so it has the first rank.

Constraints:

• 1 <= votes.length <= 1000
• 1 <= votes[i].length <= 26
• votes[i].length == votes[j].length for 0 <= i, j < votes.length.
• votes[i][j] is an English upper-case letter.
• All characters of votes[i] are unique.
• All the characters that occur in votes[0] also occur in votes[j] where 1 <= j < votes.length.

It is clear that this is a sorting problem. Eventually we should have a set of teams from A..Z with a "rank" associated to each team based on the votes. Then all we need to do is sort based on the rank.
In order to calculate this rank, though, we should think about the mathematics here. We want to ensure that a vote for the 1st position, for example, is infinitely higher than a vote for the 2nd position, and so on. Also, we want to make sure that if after all the votes there is still a tie, we untie based on the alphabetical position of the letters.
In order to do all that, we'll make use of big, big numbers (hence, make sure to use System.Numerics BigInteger). Let's assume that we have all the letters in the input, hence we have 26 letters. In order to account for the vote in the first position, the rank that we'll encode will be:

1001 ^ 26

And for the second position it will be 1001 ^ 25. We claim that this will ensure that 1 vote for first position is better than all other votes for second position. Suppose that "A" gets voted for first, hence:

A -> 1001 ^ 26

And "B" gets 1000 votes for second place, hence

B -> 1000 * (1001 ^ 25) which is less than 1001 * (1001 ^ 25) = 1001 ^ 26

Hence, A > B (since 1001 > 1000). We also add the initial values for the letters from 25..0 in order to account for the alphabetical order.

We use the rank as the priority in a priority queue (modified to take a BigInteger as a priority).

When we run this algorithm, it is clear that it runs in linear time with constant space (since we have max of 26 letters). Code is below, cheers, ACC.

public class Solution
{
    public string RankTeams(string[] votes)
    {
        BigInteger[] rank = new BigInteger[26];

        //Alphabetical tiebreak
        for (int i = 0; i < 26; i++)
        {
            rank[i] = 25 - i;
        }

        //Calculation
        for (int pos = 0; pos < votes[0].Length; pos++)
        {
            int exp = 26 - pos;
            int seed = 1001;

            for (int i = 0; i < votes.Length; i++)
            {
                int index = (int)(votes[i][pos] - 'A');
                rank[index] += BigInteger.Pow(seed, exp);
            }
        }

        //Sort using the pQueue
        PriorityQueue pQueue = new PriorityQueue();
        for (int i = 0; i < votes[0].Length; i++)
        {
            int index = (int)(votes[0][i] - 'A');
            pQueue.Enqueue(index, rank[index]);
        }

        string retVal = "";
        while (pQueue.Count > 0)
        {
            int index = (int)pQueue.Dequeue();
            retVal += ((char)(index + 'A')).ToString();
        }

        return retVal;
    }
}
public class PriorityQueue
{
    public struct HeapEntry
    {
        private object item;
        private BigInteger priority;
        public HeapEntry(object item, BigInteger priority)
        {
            this.item = item;
            this.priority = priority;
        }
        public object Item
        {
            get
            {
                return item;
            }
        }
        public BigInteger 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 long weight*/)
    {
        object result = heap[0].Item;
        //weight = heap[0].Priority;
        count--;
        trickleDown(0, heap[count]);
        return result;
    }

    public void Enqueue(object item, BigInteger 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);
    }
}