Indicate the time efficiency classes of the three main opera

Indicate the time efficiency classes of the three main operations (insert, getMax, deleteMax) of a priority queue implemented as an unsorted array, a sorted array, a binary search tree, an AVL tree, and a heap.

Solution

1.For unsorted array

a)insert->O(1)->1 step to delete

b)getMax->0(N)->total number of comparisions-N

c)deleteMax->0(1)

2.For sorted array:

a)insert->O(N)

b)getmax->O(1)->the array is sorted already

c)deleteMax->O(N)

3.Binary search tree

a)insert->O(N)

b)getMax->O(N)- depth first search into the tree

c)deleteMax->O(N)->n comparisions

4.AVL tree

a)insert->O(log n)

b)getMax->O(n)->N comparisions here

c)deleteMax->O(N)->going into depth

5.Heap

a)insert->O(log n)

b)getmax->O(LOG 2 N)

c)deletemax->O(log n)**