ヒープでいちばん重い 2 つを打ち合わせて最後に残る重さを求める

from heapq import heapify
from heapq import heappop
from heapq import heappush


def last_stone(weights):
    h = [-w for w in weights]
    heapify(h)
    while len(h) > 1:
        a = -heappop(h)
        b = -heappop(h)
        if a != b:
            heappush(h, b - a)
    return -h[0] if h else 0

function lastStone(weights) {
  const h = [];
  for (const w of weights) {
    push(h, w);
  }
  while (h.length > 1) {
    const a = pop(h);
    const b = pop(h);
    if (a !== b) {
      push(h, a - b);
    }
  }
  return h.length ? h[0] : 0;
}

function push(h, x) {
  h.push(x);
  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;
  }
}

function pop(h) {
  const top = h[0];
  const last = h.pop();
  if (h.length === 0) {
    return top;
  }
  h[0] = last;
  let i = 0;
  while (true) {
    let s = i;
    const l = 2 * i + 1;
    const r = l + 1;
    const n = h.length;
    if (l < n && h[l] > h[s]) {
      s = l;
    }
    if (r < n && h[r] > h[s]) {
      s = r;
    }
    if (s === i) {
      return top;
    }
    [h[s], h[i]] = [h[i], h[s]];
    i = s;
  }
}

import "container/heap"

type maxHeap []int

func (h maxHeap) Len() int {
	return len(h)
}

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

func (h maxHeap) Swap(
	i, j int,
) {
	h[i], h[j] = h[j], h[i]
}

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

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

func lastStone(
	weights []int,
) int {
	h := maxHeap(append(
		[]int{}, weights...))
	heap.Init(&h)
	for h.Len() > 1 {
		a := heap.Pop(&h).(int)
		b := heap.Pop(&h).(int)
		if a != b {
			heap.Push(&h, a-b)
		}
	}
	if h.Len() == 0 {
		return 0
	}
	return h[0]
}