JavaScript Priority Queue Solution O(N)
javascript\n/**\n * @param {number[]} stones\n * @return {number}\n */\nvar lastStoneWeight = function(stones) {\n  const heap = new MaxHeap(stones);\n  while (
```javascript\n/**\n * @param {number[]} stones\n * @return {number}\n */\nvar lastStoneWeight = function(stones) {\n  const heap = new MaxHeap(stones);\n  while (heap.size() > 1) {\n    const max1 = heap.poll();\n    const max2 = heap.poll();\n    if (max1 > max2) heap.offer(max1 - max2);\n  }\n  return heap.size() === 1 ? heap.poll() : 0;\n};\n\nclass MaxHeap {\n  constructor(data = []) {\n    this.data = data;\n    this.comparator = (a, b) => b - a;\n    this.heapify();\n  }\n\n  // O(nlog(n)). In fact, O(n)\n  heapify() {\n    if (this.size() < 2) return;\n    for (let i = 1; i < this.size(); i++) {\n      this.bubbleUp(i);\n    }\n  }\n\n  // O(1)\n  peek() {\n    if (this.size() === 0) return null;\n    return this.data[0];\n  }\n\n  // O(log(n))\n  offer(value) {\n    this.data.push(value);\n    this.bubbleUp(this.size() - 1);\n  }\n\n  // O(log(n))\n  poll() {\n    if (this.size() === 0) return null;\n    const result = this.data[0];\n    const last = this.data.pop();\n    if (this.size() !== 0) {\n      this.data[0] = last;\n      this.bubbleDown(0);\n    }\n    return result;\n  }\n\n  // O(log(n))\n  bubbleUp(index) {\n    while (index > 0) {\n      const parentIndex = (index - 1) >> 1;\n      if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {\n        this.swap(index, parentIndex);\n        index = parentIndex;\n      } else {\n        break;\n      }\n    }\n  }\n\n  // O(log(n))\n  bubbleDown(index) {\n    const lastIndex = this.size() - 1;\n    while (true) {\n      const leftIndex = index * 2 + 1;\n      const rightIndex = index * 2 + 2;\n      let findIndex = index;\n      if (\n        leftIndex <= lastIndex &&\n        this.comparator(this.data[leftIndex], this.data[findIndex]) < 0\n      ) {\n        findIndex = leftIndex;\n      }\n      if (\n        rightIndex <= lastIndex &&\n        this.comparator(this.data[rightIndex], this.data[findIndex]) < 0\n      ) {\n        findIndex = rightIndex;\n      }\n      if (index !== findIndex) {\n        this.swap(index, findIndex);\n        index = findIndex;\n      } else {\n        break;\n      }\n    }\n  }\n\n  // O(1)\n  swap(index1, index2) {\n    [this.data[index1], this.data[index2]] = [\n      this.data[index2],\n      this.data[index1]\n    ];\n  }\n\n  // O(1)\n  size() {\n    return this.data.length;\n  }\n}\n```\n\n* 70/70 cases passed (56 ms)\n* Your runtime beats 84.25 % of javascript submissions\n* Your memory usage beats 100 % of javascript submissions (35 MB)
['JavaScript']