A linked list is a random-memory traversal every time you do "node = node->next".

You can grossly mitigate the random-memory read/write by using unrolled linked lists (https://en.wikipedia.org/wiki/Unrolled_linked_list).

Or, instead of using binary-heaps, use d-heaps: https://en.wikipedia.org/wiki/D-ary_heap