I have been reading about trees and found dictionary operations like search, find, and delete take log(n) time in a balanced binary search tree.
Similar is the time complexities in the case of Heaps. So, why do we need them when we have a sorted structure(BSTs) that provides identical time complexities for other operations?
Why can't we just use a Balanced BST to build priority queues?
You absolutely could build a priority queue from a balanced binary search tree. However, while the big-O runtimes of its operations would still be O(log n), the wall-clock runtime of the tree-based heap would be much higher than that of a traditional binary heap for several reasons:
A traditional binary heap with n elements in it has height at most log2 (n + 1). All self-balancing BST structures that support insertions and deletions in time O(log n) have tree heights that are allowed to get bigger than this. For example, AVL trees have heights up to roughly 1.44 times that of a binary heap, and red/black tree heights can be as high as 2 times that of a binary heap. This means that each individual operation on a tree-based heap may have to do more work to traverse from the top of the tree to the bottom.
Binary heaps are complete binary trees and thus can be represented compactly in an array. This decreases the number of memory allocations needed when doing insertions and deletions and means that heaps have somewhat decent locality of reference when interacting with processor caches. Self-balancing BSTs don’t have this shape and thus require allocations every time a new item is inserted. This decreases locality of reference and is much slower because of the costs of the allocations.
As a consequence of the above point, binary heaps typically use much less memory than binary search trees. In the worst case, a binary heap holding n items requires space for 2n items (because of the use of a backing dynamic array). A binary search tree needs space for n items and 2n pointers, which is typically bigger than the space needed for the dynamic array.
Self-balancing BSTs are designed to stay balanced regardless of what sequence of insertions or deletions are performed, and thus usually involve some complex case logic and pointer rearrangement. Binary heaps, on the other hand, have extremely simple rules for insertions and deletions and the algorithms are much simpler.
Binary search trees have to keep all their elements in fully sorted order at all times, whereas binary heaps do not. This means that it’s possible to build a binary heap from scratch in time O(n), whereas creating a BST from scratch takes time Ω(n log n) in the worst case.
For all of these reasons, binary heaps end up significantly outperforming balanced BSTs when used for priority queues. But it’s great that you’re thinking about this!
