1046. Last stone weight

static void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

static void siftDown(int *h, int n, int i) {
  for (;;) {
    int max = i, l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && h[l] > h[max])
      max = l;
    if (r < n && h[r] > h[max])
      max = r;
    if (max == i)
      return;
    swap(&h[max], &h[i]);
    i = max;
  }
}

static void siftUp(int *h, int i) {
  while (i > 0 && h[(i - 1) / 2] < h[i]) {
    swap(&h[(i - 1) / 2], &h[i]);
    i = (i - 1) / 2;
  }
}

static int pop(int *h, int *n) {
  int top = h[0];
  h[0] = h[--*n];
  siftDown(h, *n, 0);
  return top;
}

// uses stones itself as a max-heap
int lastStoneWeight(int *stones, int stonesSize) {
  int n = stonesSize;
  for (int i = n / 2 - 1; i >= 0; i--)
    siftDown(stones, n, i);

  while (n > 1) {
    int y = pop(stones, &n);
    int x = pop(stones, &n);
    if (y != x) {
      stones[n] = y - x;
      siftUp(stones, n++);
    }
  }

  return n == 0 ? 0 : stones[0];
}

#include <queue>
#include <vector>

using namespace std;

class Solution {
public:
  int lastStoneWeight(vector<int> &stones) {
    priority_queue<int> pq(stones.begin(), stones.end());

    while (pq.size() > 1) {
      int y = pq.top();
      pq.pop();
      int x = pq.top();
      pq.pop();
      if (y != x)
        pq.push(y - x);
    }

    return pq.empty() ? 0 : pq.top();
  }
};

package heaps

import (
    "container/heap"
    "sort"
)

type maxHeap struct{ sort.IntSlice }

func (h maxHeap) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }

func (h *maxHeap) Push(x any) { h.IntSlice = append(h.IntSlice, x.(int)) }

func (h *maxHeap) Pop() any {
    old := h.IntSlice
    x := old[len(old)-1]
    h.IntSlice = old[:len(old)-1]
    return x
}

func lastStoneWeight(stones []int) int {
    pq := &maxHeap{stones}
    heap.Init(pq)

    for pq.Len() > 1 {
        y := heap.Pop(pq).(int)
        x := heap.Pop(pq).(int)
        if y != x {
            heap.Push(pq, y-x)
        }
    }

    if pq.Len() == 0 {
        return 0
    }
    return pq.IntSlice[0]
}

import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int s : stones)
            pq.offer(s);

        while (pq.size() > 1) {
            int y = pq.poll();
            int x = pq.poll();
            if (y != x)
                pq.offer(y - x);
        }

        return pq.isEmpty() ? 0 : pq.peek();
    }
}

class MaxHeap {
  constructor() {
    this.data = [];
  }

  size() {
    return this.data.length;
  }

  top() {
    return this.data[0];
  }

  push(val) {
    const h = this.data;
    h.push(val);
    let i = h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (h[p] >= h[i]) break;
      [h[p], h[i]] = [h[i], h[p]];
      i = p;
    }
  }

  pop() {
    const h = this.data;
    const top = h[0];
    const last = h.pop();
    if (h.length === 0) return top;
    h[0] = last;
    let i = 0;
    for (;;) {
      let max = i;
      const l = 2 * i + 1,
        r = 2 * i + 2;
      if (l < h.length && h[l] > h[max]) max = l;
      if (r < h.length && h[r] > h[max]) max = r;
      if (max === i) return top;
      [h[max], h[i]] = [h[i], h[max]];
      i = max;
    }
  }
}

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function (stones) {
  const pq = new MaxHeap();
  for (const s of stones) pq.push(s);

  while (pq.size() > 1) {
    const y = pq.pop();
    const x = pq.pop();
    if (y !== x) pq.push(y - x);
  }

  return pq.size() === 0 ? 0 : pq.top();
};

import heapq
from typing import List


class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        pq = [-s for s in stones]  # negate for a max-heap
        heapq.heapify(pq)

        while len(pq) > 1:
            y = -heapq.heappop(pq)
            x = -heapq.heappop(pq)
            if y != x:
                heapq.heappush(pq, -(y - x))

        return -pq[0] if pq else 0

use std::collections::BinaryHeap;

impl Solution {
    pub fn last_stone_weight(stones: Vec<i32>) -> i32 {
        let mut pq = BinaryHeap::from(stones);

        while pq.len() > 1 {
            let y = pq.pop().unwrap();
            let x = pq.pop().unwrap();
            if y != x {
                pq.push(y - x);
            }
        }

        pq.pop().unwrap_or(0)
    }
}