Использование heapsort vs js объекта для реализации приоритетной очереди в javascript?

Пытаемся разобраться, какой из них оптимальнее использовать и реализовать.

Другой способ, которым я думал, - использовать объект js. Вставив значение приоритета (целое/число) в качестве ключа в объект js.

Учитывая, что при перечислении объекта js в ES6 мы можем получить ключи, представляющие собой целочисленные индексы (если применимо), в порядке возрастания. Вводит ли ES6 четко определенный порядок перечисления свойств объекта?

Мы можем использовать объект js с целочисленными ключами в качестве приоритетной очереди и получить время выполнения O(n). сложность Object.keys()?

const priorityQueue = {3:1,20:1,10:1,15:1,};
console.log(Object.keys(priorityQueue));
priorityQueue[5]=1;
console.log(Reflect.ownKeys(priorityQueue));


person divyanshch    schedule 08.12.2020    source источник
comment
Что быстрее?   -  person VLAZ    schedule 08.12.2020
comment
И как вы собираетесь реализовать в своей версии объектного ключа, когда в очередь ставится несколько записей с одинаковым приоритетом?   -  person FZs    schedule 08.12.2020
comment
@FZs Я думаю, что это можно оставить для реализации в случае использования, у нас может быть либо массив, либо одно значение.   -  person divyanshch    schedule 08.12.2020
comment
В чем именно заключается ваш вопрос?   -  person Bergi    schedule 08.12.2020
comment
Главный вопрос заключается в том, верен ли мой анализ и целесообразно ли использовать объект вместо кучи для реализации приоритетной очереди. Если анализ верен, он делает Object лучшим вариантом использования, поскольку они оба будут использовать n пространства для сортировки памяти или объекта для хранения, но в этом случае объект выиграет из-за (n) поиска и (1) вставки [если нет коллизий ].   -  person divyanshch    schedule 08.12.2020
comment
Кажется, вы читали неправильный ответ на вопрос сложность Object.keys()?. правильный объясняет, как в вашем случае использования Object.keys() на самом деле является O(n log n).   -  person Bergi    schedule 08.12.2020
comment
Это кажется оправданным @Bergi. Я также смотрел на Reflect.ownKeys, который также является O (n). stackoverflow.com/questions/30076219/   -  person divyanshch    schedule 08.12.2020
comment
Нет, по тем же причинам. (В ответе, который вы связали, даже не упоминается сложность?)   -  person Bergi    schedule 08.12.2020
comment
@Bergi в ссылке, которой вы поделились, говорится, что она надежна, и в случае, когда ключи названы свойствами, это (nLog n). если я не читаю это неправильно.   -  person divyanshch    schedule 08.12.2020
comment
Да, это зависит. Вы получаете O(n) только для достаточно плотных целочисленных/индексированных свойств, то есть в основном для массива, но ваш пример const priorityQueue не выглядит очень плотным, и я не уверен, почему вы ожидаете общий случай быть.   -  person Bergi    schedule 08.12.2020
comment
@Bergi Берги, можно ли предположить, что наихудший сценарий - O (n log n) при использовании Object.keys ()? Если да, то следующий вопрос: зачем сортировать по пирамиде, если можно просто использовать js Object? Поскольку время выполнения и сложность данных будут одинаковыми. Runtime: (n log n) data: (n)   -  person divyanshch    schedule 09.12.2020
comment
Потому что куча обеспечивает легкий доступ к элементам по индексу, а не по приоритету, особенно доступ к первому элементу. Потому что он работает с приоритетами, которые не являются положительными целыми числами. Потому что его можно многократно повторять в линейном времени.   -  person Bergi    schedule 09.12.2020