Compare Heaps vs Arrays to implement Priority Queue

Heap is generally preferred for priority queue implementation because heaps provide better performance compared arrays or linked lists:

• In Array:
• insert() operation can be implemented by adding an item at end of array in O(1) time.
• getMax() operation can be implemented by linearly searching the highest priority item in array. This operation takes O(n) time.
• deleteMax() operation can be implemented by first linearly searching an item, then removing the item by moving all subsequent items one position back.

• In a Binary Heap:
• getMax() can be implemented in O(1) time,
• insert() can be implemented in O(log n) time and
• deleteMax() can also be implemented in O(log n) time.