Menu
When making a binary max heap, why is it better to implement it as a array based, and not a tree based (tree based as in, each node also having a pointer to it's parent)? In terms of run time analysis, memory usage, performance...
For binary max heap, the running times are:
For a tree implementation
Can anyone explain in detail?
306
So why is Binary Heap Preferred for Priority Queue? Since Binary Heap is implemented using arrays, there is always better locality of reference and operations are more cache friendly. Although operations are of same time complexity, constants in Binary Search Tree are higher. We can build a Binary Heap in O(n) time.
Why Array? Since a Binary Heap is a Complete Binary Tree, it can be easily represented as an array and array-based representation is space-efficient. Level Order Traversal of the heap will give the order in which elements are filled in the array.
The fundamental distinction is that whereas the Binary Search Tree does not allow duplicates, the Heap allows. The BST is ordered, while Heap is not. So, if order is important, BST is the way to go.
Heaps use less memory. They can be implemented as arrays and thus there is no overhead for storing pointers. (A binary tree CAN be implemented as an array, but there is likely to be many empty "gaps" which could waste even more space than implementing them as nodes with pointers).
The tree uses more time and memory. The complexities are the same, but the constant factors are different.
The pointers of the tree use a lot of memory, compared to the array-based heap, where you barely need any additional space but the one taken by the values themselves. And manipulating these pointers takes time too. Allocating and deallocating nodes might take some time and space also...
In addition, there's no guarantee that the nodes of the tree will be together in memory. If any of the two alternatives takes benefit of the cache, it is the array-based heap.
63
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
