Binary Heap and Priority Queues

Question

I am new to Heaps, Binary Heap and I am trying to understand why do we need to implement Priority Queue using a Binary Heap. I also understand that the underlying data structure of Binary Heap is again an array.

So my question is why can we not use an array, sorted in either descending (for max heap) or ascending (for min heap) order to represent a priority queue ? I might be wrong here, but I think the time complexity of the operations like, findMax, findMin, insert and delete will remain almost the same if implemented this way. So can we not not a use a sorted array to represent the priority queue ?

I have already read this answer: Heap vs Binary Search Tree (BST)

Answer 1

Both has its own advantages and disadvantages:

• Trees are more flexible and, if they are balanced, have better performance, with worst-case logarithmic search, insertion, and delete. All these benefits have a price. In trees, lists, and graphs every node requires extra space for the pointers and each node is placed in random places, which causes memory overhead

• All the elements in the array are contiguous in memory, and this means lower latency when reading them. Use a sorted array if deletions and insertions are not going to happen often