CODEWITHSUNDEEP
data-structuresheap
frei
frei

Reputation: 536

Is it possible to make a heap as a tree with parent references?

I know that heaps use a basic array structure as an underlying thing so that you can always find a reference to the parent by just calculating based on index, but is there a way to implement a heap as a Tree with no indexing and just referencing the parent node through the data structure?

In a similar vein, could search trees also use the array indexing structure instead of left right node references? I'm not sure conceptually why one was taught one way and the other another way / what about the data structure makes it so that this isn't the standard implementation. I assume its because you can always access a heap element in O(1) time, and you only ever use the heap to get one element.

Upvotes: 0

Views: 50

Answers (1)

Raj
Raj

Reputation: 674

is there a way to implement a heap as a Tree with no indexing and just referencing the parent node through the data structure?

Yes, you could implement a heap in that way. But that's not recommended because a heap by it's definition is an Almost complete Binary tree. So by using array based indexing, there is no wastage of memory and ease in implementation.

could search trees also use the array indexing structure instead of left right node references

Yes, but a search tree can be skewed, array implementation leads to huge memory waste.

Upvotes: 1

Related Questions