DEV Community

Santiago Salazar Pavajeau
Santiago Salazar Pavajeau

Posted on

Using a heap to find the minimum cost to modify an array

Javascript doesn't have a heap data structure like java does PriorityQueue so an external library or an own implementation is needed.

const minCost = (numbers) => {
    return Math.min(up(numbers, numbers.length), down(numbers, numbers.length))
}

const down = (numbers, length) => {
    let sum = 0
    let diff = 0

    let minQueue = new MinBinaryHeap()

    for(let i = 0; i < length; i++){
        // console.log(minQueue.getTop())
        if(!minQueue.isEmpty() && minQueue.getTop() <= numbers[i]){
            diff = numbers[i] - minQueue.getTop()
            sum += diff
            minQueue.getTopElementAndReorder()
            minQueue.insertElement(numbers[i])
        }
        minQueue.insertElement(numbers[i])
    }
    return sum
}

const up = (numbers, length) => {
    let sum = 0
    let diff = 0

    let maxQueue = new MaxBinaryHeap()

    for(let i = 0; i< length; i++){
        if(!maxQueue.isEmpty() && maxQueue.getTop() >= numbers[i]){
            diff = maxQueue.getTop() - numbers[i]
            sum += diff
            maxQueue.getTopElementAndReorder()
            maxQueue.insertElement(numbers[i])
        }
        maxQueue.insertElement(numbers[i])
    }
    return sum
}
Enter fullscreen mode Exit fullscreen mode

This algorithm calculates the minimum amount of changes that are needed to make an array ascending or descending.

Each value in the array is added to the binary heap then if there is a larger or lower (correspondingly) number in the heap than the current value then the difference between the values is accumulated in the sum variable.

Using the heap allows for storing and retrieveing elements relatively fast and always in a sorted manner.

Here is my max binary heap and min binary heap priority queue implementation

Top comments (0)