Compare Heaps vs Arrays to implement Priority Queue

Technology CommunityCategory: Data StructuresCompare Heaps vs Arrays to implement Priority Queue
VietMX Staff asked 5 months ago

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.