Logo Questions Linux Laravel Mysql Ubuntu Git Menu
HTML CSS JAVASCRIPT SQL PYTHON PHP BOOTSTRAP JAVA JQUERY R React Kotlin
 

Why is a binary heap better as an array than a tree?

Tags:

big-o

tree

heap

binary-tree

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:

  • insert: O(lg n)
  • delete min: O(lg n)
  • merge: O(n)

For a tree implementation

  • insert: O(lg n)
  • delete min: O(lg n)
  • merge: O(n)

Can anyone explain in detail?

like image 306
omega Avatar asked Feb 05 '13 23:02

omega

People also ask

Why is a binary heap better?

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 is used for binary heap?

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.

What is the difference between binary tree and binary heap?

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.

What are the advantages of heap data structure over binary tree?

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).

1 Answers

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.

like image 63
comocomocomocomo Avatar answered Oct 18 '22 06:10

comocomocomocomo
Sign in to Comment

Related questions

d3.js rewriting zoom example in version4
algorithm to find max independent set in a tree
B-tree class in C# standard libraries? [closed]
OO Design Question -- Parent/Child(ren) -- Circular?
How to get a tree in HTML using pure CSS
Fast Relational method of storing tree data (for instance threaded comments on articles)
What is the difference btw "Order" and "Degree" in terms of Tree data structure
traversing a non binary tree in java [closed]
Recursive breadth-first travel function in Java or C++?
Print the biggest K elements in a given heap in O(K*log(K))?
PHP - How to build tree structure list?
Real world examples of tree structures
How to match SURF interest points to a database of images
How to, given a predetermined set of keys, reorder the keys such that the minimum number of nodes are used when inserting into a B-Tree?
print a binary tree on its side
Tree Structure and Recursion
How To Develop A Database Schema For A Tree Structure(Directed acyclic graph)
Hierarchical data: efficiently build a list of every descendant for each node
Uniqueness of Inorder, Preorder, and Postorder traversal with null elements

Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!