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)
You can use an array to represent a priority queue, but you lose a lot of efficiency when you do so. Imagine you insert something into an array, and it has higher priority than any object in the queue. It needs to go at index 0, the object at index 0 needs to go to index 1, and so on.
This is O(n), but if you insert a value into the front of a priority queue composed of a binary tree, you only need to change lg(n) nodes, making binary trees much better at modeling priority queues than arrays are.
Deleting elements have a similar time complexity.
Accessing the back of the priority queue is constant time if it's implemented with an array, but O(n) time if it's implemented with a binary tree, so this is a significant advantage arrays have over binary trees, but priority queues in general don't need to access the element with the least priority much of the time, and so binary trees represent priority queues more efficiently than arrays in general.