CODEWITHSUNDEEP
c++data-structures
Xiangyu Zhang
Xiangyu Zhang

Reputation: 75

Implement BST by array and implement heap by linked list

I am currently learning data structure and trying to implement a BST and max-heap(use BST as base class). But I accidentally found it seems impossible to derive heap from BST. Almost all the implementation for heap are based on array rather then using pointers point to left and right, and most of BST are based on pointers rather than array.

So my question is why I have to use array to realize a heap? And, in realizing BST, why people choose to use pointers point to left and right rather array? I know use array to realize BST may cost more space, and it is harder to implement remove function, is there any more reason for that?

Thank you so much!

Upvotes: 0

Views: 176

Answers (1)

Sumeet
Sumeet

Reputation: 8292

The main reason standard implementation of binary heaps is done using arrays is because heaps are complete binary trees.

Because complete binary trees always grow level by level(Meaning:First the parent level will be filled with nodes and only then the child level is filled).

Therefore,We are able to use arrays where for a node at position i, the left child is found at position 2*i and right child is found at position 2*i+1.

The reason that binary search trees is implemented using pointers and not using arrays is because binary search trees are not guaranteed to be complete binary trees

Upvotes: 2

Related Questions