Implementing priority queue using max heap vs balanced BST

Question

Balanced BST and max heap both perform insert and delete in O(logn). However, finding max value in a max heap is O(1) but this is O(logn) in balanced BST.

If we remove the max value in a max heap it takes O(logn) because it is a delete operation.

In balanced BST, deleting the max element = finding max value + delete; it equals logn + logn reduces to O(logn). So even deleting the max value in balanced BST is O(logn).

I have read one such application of max heap is a priority queue and its primary purpose is to remove the max value for every dequeue operation. If deleting max element is O(logn) for both max heap and balanced BST, I have the following questions

• What is the purpose of a max heap in the priority queue just because it is easy to implement rather than using full searchable balanced BST?

• Since there is no balancing factor calculation, the max heap can be called an unbalanced binary tree?

• Every balanced BST can be used as a priority queue and which is also searchable in O(logn) however max heap search is O(n) correct?

All the time complexities are calculated for worst-case. Any help is greatly appreciated.

Answer 1

What is the purpose of a max heap in the priority queue just because it is easy to implement rather than using full searchable balanced BST?

Nope. Max heap fits better, since it is carefully instrumented to return next (respecting priority) element ASAP, in O(1) time. That's what you want from the simplest possible priority queue.

Since there is no balancing factor calculation, the max heap can be called an unbalanced binary tree?

Nope. There is a balance as well. Long story short, balancing a heap is done by shift-up or shift-down operations (swapping elements which are out of order).

Every balanced BST can be used as a priority queue and which is also searchable in O(logn) however max heap search is O(n) correct?

Yeah! As well as linked list could be used or array. It is just gonna be more expensive in terms of O-notation and much slower on practice.

Answer 2

What is the purpose of a max heap in the priority queue just because it is easy to implement rather than using full searchable balanced BST?

Some advantages of a heap are:

• Given an unsorted input array, a heap can still be built in O(n) time, while a BST needs O(nlogn) time.

• If the initial input is an array, that same array can serve as heap, meaning no extra memory is needed for it. Although one could think of ways to create a BST using the data in-place in the array, it would be quite odd (for primitive types) and give more processing overhead. A BST is usually created from scratch, copying the data into the nodes as they are created.

  Interesting fact: a sorted array is also a heap, so if it is known that the input is sorted, nothing needs to be done to build the heap.

• A heap can be stored as an array without the need of storing cross references, while a BST usually consists of nodes with left & right references. This has at least two consequences:

  • The memory used for a BST is about 3 times greater than for a heap.
  • Although several operations have the same time complexity for both heap and BST, the overhead for adapting a BST is much greater, so that the actual time spent on these operations is a (constant) factor greater in the BST case.

Since there is no balancing factor calculation, the max heap can be called an unbalanced binary tree?

A heap is in fact a complete binary tree, so it is always as balanced as it can be: the leaves will always be positioned in the last or one-but-last level. A self-balancing BST (like AVL, red-black,...) cannot beat that high level of balancing, where you will often have leaves occurring at three levels or even more.

Every balanced BST can be used as a priority queue and which is also searchable in O(logn) however max heap search is O(n) correct?

Yes, this is true. So if the application needs the search feature, then a BST is superior.