// MaxHeap implementation using a binary heap
class MaxHeap {
    constructor() {
        this.heap = [];
    }

    insert(value) {
        this.heap.push(value);
        this._bubbleUp();
    }

    extractMax() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        const max = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._bubbleDown();
        return max;
    }

    _bubbleUp() {
        let index = this.heap.length - 1;

        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex] >= this.heap[index]) break;

            [this.heap[parentIndex], this.heap[index]] =
                [this.heap[index], this.heap[parentIndex]];

            index = parentIndex;
        }
    }

    _bubbleDown() {
        let index = 0;
        const length = this.heap.length;

        while (true) {
            const left = 2 * index + 1;
            const right = 2 * index + 2;
            let largest = index;

            if (left < length && this.heap[left] > this.heap[largest]) {
                largest = left;
            }

            if (right < length && this.heap[right] > this.heap[largest]) {
                largest = right;
            }

            if (largest === index) break;

            [this.heap[index], this.heap[largest]] =
                [this.heap[largest], this.heap[index]];

            index = largest;
        }
    }

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

// Solves the Last Stone Weight problem using the MaxHeap
function lastStoneWeight(stones) {
    const heap = new MaxHeap();

    for (const stone of stones) {
        heap.insert(stone);
    }

    while (heap.size() > 1) {
        const stone1 = heap.extractMax();
        const stone2 = heap.extractMax();

        if (stone1 !== stone2) {
            heap.insert(stone1 - stone2);
        }
    }

    return heap.size() === 0 ? 0 : heap.extractMax();
}

// Example usage:
console.log(lastStoneWeight([2, 7, 4, 1, 8, 1])); // Output: 1