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

Question

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

Мое понимание SLL - то, что, поскольку вам, возможно, придется перебирать весь список, неэффективно реализовывать его как таковой, поэтому кучи предпочтительнее. Однако, возможно, я упускаю какие-то рассуждения и задавался вопросом, выбирал ли кто-нибудь SLL вместо кучи для приоритетной очереди?

Answer 1

В есть ситуации, когда SLL лучше, чем куча для реализации очереди с приоритетами.Например:

1. При удалении из очереди необходимо максимально быстро.Удаление из SLL - это O (1) (из начала списка / очереди), в то время как удаление из кучи - это O (log n).Я действительно столкнулся с этим, когда писал версию системного вызова alarm() для простой ОС.Я просто не мог позволить себе время поиска O (log n).С этим связано, когда вам нужно удалить несколько элементов одновременно.Удаление k элементов из SLL занимает время O (k), а для кучи - время O (k log n).
2. Проблемы с памятью.Традиционная реализация кучи min или max включает массив, размер которого необходимо изменять по мере роста кучи.Если вы не можете позволить себе время, необходимое для большого realloc, то эта стратегия отсутствует.Если вы реализуете кучу как двоичное дерево, то для SLL вам понадобится два указателя вместо одного.
3. Когда вам нужно поддерживать несколько приоритетов.Относительно легко отслеживать одни и те же узлы в разных связанных списках.Делать это с кучей гораздо сложнее.

Answer 2

В колледже мне сказали, что единственная причина, по которой нас заставили использовать связанные списки, - помочь нам в понимании указателей.