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

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

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