Как при помощи кучи найти минимальное значение двумерного массива и оценить время работы алгоритма?

Question

[barakuda1]

Приветствую всех!

Собственно, задача стоит такая: при помощи кучи найти минимальное значение двумерного массива и оценить время работы алгоритма.

const numbers = [[2, 1, 2], [0, 4, 5] ];

var A = Math.min.apply(null,numbers[0]);
var B = Math.min.apply(null,numbers[1]);

if(A < B) {
    console.log(A);
}else
if(A > B) {
    console.log(B);
}else{
    console.log("Найдены одинаковые минимальные значения: " + A + "," + B);
}

Значения выводит корректно, но правильно ли я понял задачу, написав такой код?
Как оценить время работы алгоритма?

Comments

[WbICHA]

Как оценить время работы алгоритма?

Тут оценивать нечего, он выполняться будет за 0-1мс.
К тому же тут явно подразумевается самому найти минимальное значение, а не использовать встроенные методы.

[alexalexes]

Собственно, а где у вас структура данных - куча (хотя бы двоичная)?
Этап формирования кучи?
Этап поиска элемента в куче?

[barakuda1]

alexalexes,

const findMin = () => {
    const numbers = [[1, 8, 2], [6, 4, 9] ];
    const A = Math.min.apply(null,numbers[0]);
    const B = Math.min.apply(null,numbers[1]);
    
    if(A < B) {
        return A;
    }else
    if(A > B) {
        return B;
    }
}

console.log(findMin());

А если так?

[WbICHA]

barakuda1, и что изменилось?

[barakuda1]

alexalexes, то есть по коду выше, у нас появляется фрейм findMin, в куче хранятся переменные numbers, A, B.

[WbICHA]

barakuda1, вообще тебе бы перечитать задачу:

найти минимальное значение

Про проверку на равенство нигде ничего не написано.

[alexalexes]

А где вспомогательная структура данных - куча?
Ее в этом куске кода нет.
Вам нужно изучить, как создать бинарное дерево, как его наполнить и как его обойти.
Из предложенного кода у вас останется в качестве входных данных:
const numbers = [[1, 8, 2], [6, 4, 9] ];
И где-то в методе наполнения и методе обхода у вас будет использоваться:

if(A < B) {
        return A;
    }else
    if(A > B) {
        return B;
    }

А остальное - нужно написать своими ручками.

[Alexandroppolus]

Бессмысленное условие. Чтобы найти минимальное значение в двумерном массиве, надо просто обойти его вложенным циклом. Все прочие решения (с кучами и т.д.) будут ересью и говнокодом.

[barakuda1]

Alexandroppolus, такова задача.

[barakuda1]

WbICHA, здесь прибегнуть к куче нужно, по-другому никак.

[alexalexes]

Ересь-не ересь. Смысл не решить задачу, наработать навык работы с деревьями.

[Alexandroppolus]

навык работы с деревьями

для бинарной кучи как раз не понадобится строить дерево (именно как структуру данных)

Answer 1

[Alexandroppolus]

куча так куча...

function siftDown(arr, i) {
    let chi = i * 2 + 1;
    while (chi < arr.length) {
        const minChildIdx = chi < arr.length - 1 && arr[chi + 1] < arr[chi] ? chi + 1 : chi;
        const chv = arr[minChildIdx];
        if (arr[i] <= chv) break;
        arr[minChildIdx] = arr[i];
        arr[i] = chv;
        i = minChildIdx;
        chi = i * 2 + 1;
    }
}

function heapify(arr) {
    for (let i = Math.floor(arr.length / 2); i >= 0; --i) {
        siftDown(arr, i);
    }
}

function findMinWithHeap(arr) {
    const heap = arr.flat();
    heapify(heap);
    return heap[0];
}

console.log(findMinWithHeap([[2, 1, 2], [0, 4, 5] ]));

время работы O(N), где N - сколько всего элементов в массиве. Надо объяснять почему, или и так понятно?