1

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)

Community
  • 1
  • 1
RDM
  • 1,136
  • 3
  • 28
  • 50

2 Answers2

3

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.

E.D.
  • 639
  • 6
  • 14
  • Thank you. I now somehow missed the most basic stuff that array takes O(n) time for rearranging the elements and Tress usually take log(n). Thanks for the clarification. – RDM May 18 '17 at 21:27
0

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

Yilmaz
  • 35,338
  • 10
  • 157
  • 202