Last Stone Weight, an easy LeetCode problem

Happy Sunday, folks!

In this problem, there is a very simple data structure that can be used. Here is the problem: https://leetcode.com/problems/last-stone-weight/

We have a collection of rocks, each rock has a positive integer weight.

Each turn, we choose the two heaviest rocks and smash them together.  Suppose the stones have weights x and y with x <= y.  The result of this smash is:

• If x == y, both stones are totally destroyed;
• If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left.  Return the weight of this stone (or 0 if there are no stones left.)

Example 1:

Input: [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.

Note:

1. 1 <= stones.length <= 30
2. 1 <= stones[i] <= 1000

The simplest data structure to solve this problem is a Heap, which I had implemented before as a Priority Queue. Enqueue all the stones, and start the process of dequeuing following the rules outlined in the problem statement. Straightforward. Cheers, ACC:

public class Solution
{
    public int LastStoneWeight(int[] stones)
    {
        PriorityQueue pq = new PriorityQueue(2000, true);
        foreach (int s in stones) pq.Enqueue(s, s);

        while (pq.Count > 0)
        {
            int first = (int)pq.Dequeue();
            if (pq.Count == 0) return first;
            int second = (int)pq.Dequeue();
            if (first > second)
            {
                pq.Enqueue(first - second, first - second);
            }
        }

        return 0;
    }
}

/*By-the-book PriorityQueue*/
public class PriorityQueue
{
    public struct HeapEntry
    {
        private object item;
        private long priority;
        public HeapEntry(object item, long priority)
        {
            this.item = item;
            this.priority = priority;
        }
        public object Item
        {
            get
            {
                return item;
            }
        }
        public long Priority
        {
            get
            {
                return priority;
            }
        }
    }

    private long count;
    private long capacity;
    private bool descending; //Means that the max element at the top
    private HeapEntry[] heap;

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

    public PriorityQueue(long capacity, bool descending)
    {
        this.capacity = capacity;
        this.descending = descending;
        heap = new HeapEntry[this.capacity];
    }

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

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

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

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