Last Stone Weight | Heap | Priority Queue

You are given an array of integers stones where stones[i] represents the weight of the ith stone.

We want to run a simulation on the stones as follows:

• At each step we choose the two heaviest stones, with weight x and y and smash them togethers
• If x == y, both stones are destroyed
• If x < y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

Continue the simulation until there is no more than one stone remaining.

Return the weight of the last remaining stone or return 0 if none remain.

Example 1:

Input: stones = [2,3,6,2,4]

Output: 1

Explanation:

We smash 6 and 4 and are left with a 2, so the array becomes [2,3,2,2].

We smash 3 and 2 and are left with a 1, so the array becomes [1,2,2].

We smash 2 and 2, so the array becomes [1].

Example 2:

Input: stones = [1,2]

Output: 1

Constraints:

• 1 <= stones.length <= 20
• 1 <= stones[i] <= 100

rainstorming, if we have a max heap of the stones:

where stone are organizedw
                 6  
               4   3
            2   2

            1st heavy = 6

                 4  
               2   3
            2   

            2nd heavy = 4

               3
            2       
         2

         3rd heavy = 3

               2
            2

        4rth heavy = 2

           2
        5th heavy = 2

We need to organise our stones based on their weight:

 difference =  1stHeavy - 2nd heavy
            = 6 - 4
            = 2
                        
once we calculate the difference we need to insert it back
heap.insert(difference)

Implementing Max Heap

Sorting stones by their weight:

lass Solution {
    /**
     * @param {number[]} stones
     * @return {number}
     */
    lastStoneWeight(stones) {

       
        let heap = new Heap()
        for(let stone of stones){
            heap.insert(stone)
        }

        while(1 < heap.size()){
            let heaviest = heap.pop()
            let heavier = heap.pop()
            let diff = heaviest - heavier
            heap.insert(diff)
        }
        return heap.pop()
     
}

lass Heap{
    constructor(comparator = (a, b) => b < a){
        this.comparator = comparator
        this._heap = []
    }
    _parent(node){
        return Math.floor((node -1) / 2)
    }
    _leftChild(node){
        return node * 2 + 1
    }
    _rightChild(node){
        return node * 2 + 2
    }
    _swap(i, j){
        let temp = this._heap[i] 
        this._heap[i] = this._heap[j]
        this._heap[j] = temp
    }
    size(){
        return this._heap.length
    }
    _compare(i, j){
        return this.comparator(this._heap[i], this._heap[j])
    }

   _bubbleUp(){
        // access the value at the end 
        // reorganize the heap

        let currentIndex = this.size() - 1
        while(this._compare(currentIndex, this._parent(currentIndex))){
            this._swap(currentIndex,  this._parent(currentIndex))
            currentIndex =  this._parent(currentIndex)
        }
    }

   insert(node){
        this._heap.push(node)
        this._bubbleUp()
    }
    peek(){
        return this._heap[0]
    }

45

20 14

5 18

removing 45

18*

20 14

5

reorganizing the heap i.e bubbleDown

20

18 14

5

   _bubbleDown(){
        let parentIndex = 0
        while(true){
            let greaterIndex = parentIndex
            let leftChildIndex = this._leftChild(parentIndex)
            let rightChildIndex = this._rightChild(parentIndex)

            if(this._compare(leftChildIndex, greaterIndex)){
                greaterIndex = leftChildIndex
            }

            if(this._compare(rightChildIndex,  greaterIndex)){
                greaterIndex = rightChildIndex
            }

            if(greaterIndex === parentIndex){
                break
            }
            this._swap(greaterIndex, parentIndex)
            parentIndex = greaterIndex
        }

    }

   pop(){
        this._swap(0, this.size() - 1 )
        const result = this._heap.pop()
        this._bubbleDown()
        return result
    }
}

#Heap #dataStructure #priorityQueues