Menu
In a (max) heap it is easy to find the biggest item in O(1) time, but to actually remove it you need complexity of O(log(n)).
So if the insertion and deletion from a heap is both O(log(n)), what are the advantages of a heap over binary tree for representing a priority queue?
710
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.
I've found that a skip list priority queue is often much more efficient than a binary heap. Also, pairing heap (which is not a traditional heap) is at fast or faster than binary heap, at least in my tests. Both of these do, on average, many fewer dereferences.
The heap provides multiple functions and operations than the priority queue. The priority queue provides queue-related functions. The heap implements abstract data types such as priority queue but priority queue does not implement heap. The priority queue is simpler than the heap data structure.
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).
Heaps are guaranteed to have height of log(n), because they do not need to guarantee that elements can be retrieved in sorted order though an in-order traversal, only that a node's value dominates its children's values. This allows them to have their "packed" structure as an array. A binary tree (unless it is a balanced binary tree) will usually end up with with branches that have a height larger than log(n), so even though operations have the same big O complexity, in reality the heap will be slightly faster.
Since the heap can be implemented as an array you get a huge advantage of accessing contiguous memory that is likely still in the cache rather than accessing nodes pointed to by pointers who's memory is scattered all over the place.
Heaps are simpler to implement than binary trees (especially balanced binary trees)
A disadvantage is that with heaps you are not able to do a binary search, but for a priority queue you do not need this ability.
191
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
