why are priority queues implemented as binary heap?

Question

Why do people stress that heaps are used to implement priority queues because time complexity of peeking at max/min value is O(1) .
Can't this be easily implented on a bst too , by using pointer to point at right most/left most node.

Answer 1

Given the fact that you propose a priority queue based on BST, I will try to explain you why a heap is better than a BST.

A heap is a complete tree; it is a perfectly balanced tree. Its height is log_2(n+1).

A BST approach is worthwhile if this one is balanced. The best-known technique for maintaining a BST balanced is an AVL tree. This kind of tree has a height bound of 1.44 log_2(n+2) - 0.33.

For the consultation of minimum you have a cost of O(log(n)) for a BST versus O(1) for a heap. So for this operation the heap clearly is better.

For insertion and deletion the costs are asymptotically equivalent. But the BST tends to be more expensive because its height tends to be higher than a perfectly balanced tree. In addition, an AVL tree consumes more constant time than a heap. In the AVL (and also in other balancing approaches, red-black tree, treaps, splays, etc) you perform rotations, while with the heap you perform swaps, which are cheaper than rotations.

Deletion on BST is a complicated and constantly expensive operation and could take O(log(n)) rotations. With a heap is O(log(n)) swaps, which recall are cheaper that rotations.

Eventually, in the case of an insertion, you could perform O(log(n)) swaps for the heap and at the most two rotations for the AVL. But with the insertion into an AVL you need to perform an unsuccessful search, while the heap you can directly insert the new key before starting to swap. I think that only with the insertion a BST could sometimes beat a heap. However, take in account that very probably you would use a priority queue for consultations and deletions; so, If this is the case, then surely you will recover the time you could lose when you made the insertions.

In addition, a heap is by far much easier to implement than a BST if you use an array which stores the level traversal of complete tree. In this case, you do not need pointers

Answer 2

It can, but doing it as a heap is more efficient, and arguably simpler, since the top of a heap is easier to keep track of than the leftmost element of a tree (the top of a heap is just the first element of the underlying sequence).