Why use heap instead of binary tree when implementing priority queue?

Question

It seems to me that the only advantage of heap over binary tree is to find the smallest item in the heap in complexity of O(1) instead of O(log(2)n) in binary tree.

When implementing priority queue you need to delete the smallest item each from the data structre. deleting the smallest item from a tree and both heap done in complexity of O(log(2)n). Althogh deleting item from a tree may be more complex. Deleting item with no childrens acctually very simple.

My question is why use heap instead of binary tree(which is simpler in this case) when implementing priority queue?

Answer 1

Worst case complexity in case of binary tree will be O(n) when binary tree converges to an array while in heap it remains O(log(n)). you can use balanced binary trees like red black or AVl but then it wud become more complex and would require more memory.