We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones 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 <= stones.length <= 30`

`1 <= stones[i] <= 1000`

**Solution**

Use

`Priority queue (heap)`

to simulate the process.

```
class Solution {
func lastStoneWeight(_ stones: [Int]) -> Int {
var heap = Heap<Int>(elements: stones, priorityFunction: >) // O(n)
while heap.count > 1 {
let first = heap.dequeue()! // O(logn) time
let second = heap.dequeue()! // O(logn) time
let newVal = abs(first - second)
if newVal > 0 {
heap.enqueue(newVal)
}
}
if heap.count == 0 { return 0 }
return heap.peek()!
}
}
```

Detail about how to implement `Priority Queue`

can be found here