Java – Implementing a binary heap using a linked list

algorithmbinary-treeheapjava

Possible Duplicate:
Linked list implementation of Binary Min Heap (Having trouble with manipulation…)

Greetings,

I'm having trouble figuring out an algorithm that will give me the location of a tree node in a linked list implementation of a binary heap. I've implemented a heap using arrays now I want to try using a linked list; Is there a way to find the tree node whose array index would have been i had I used an array to represent the heap?

Best Solution

What's the point? A linked list implementation will be either slower or more complex than an array-based one. If you replace the array with a simple linked list and don't add other structure your insertion time will be O(n) instead of O(log n), and then you could as well just maintain a sorted list in same O(n) complexity.