CODEWITHSUNDEEP
heappriority-queue
GKS
GKS

Reputation: 35

Why Priority queue preferred to implement using heap not by array although Heap itself implemented using array

Why Priority queue preferred to implement using heap not by the array, although Heap itself implemented using an array.

Upvotes: 0

Views: 105

Answers (1)

Jim Mischel
Jim Mischel

Reputation: 133975

The binary heap provides a partial ordering, which guarantees O(log n) insertion and O(log n) removal of the highest-priority item.

With a flat array, you have two choices:

  1. Maintain an ordered array. Insertion becomes an O(n) operation, and removal of the highest-priority item is O(1).
  2. Insert items in the order they're received. Insertion then becomes O(1), and removal of the highest-priority item is O(n).

Either of those two options makes the priority queue less efficient than if you implement a binary heap.

Upvotes: 2

Related Questions