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
}

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

Blog

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

Santiago Salazar Pavajeau

Join Our Newsletter. No Spam, Only the good stuff.

Related