4,403 views
0 votes
0 votes
which of the following data structure is efficient to implement priority queue with basic operations such as insertion,deletion and searching?

A)linked list

B)Heap

C)Sorted array

D)Unsorted array

2 Answers

1 votes
1 votes
Searching is for the highest priority element

Linked List(Single link list) : Insertion O(1), Deletion O(n), Searching O(n)

Heap : Insertion O(logn), Deletion O(logn),Searching O(1)

Sorted array : Insertion O(n), Deletion O(1), Searching O(1)

Unsorted array : Insertion O(1), Deletion O(n), Searching O(n)

Heap would be the best choice because as n approaches a very large number say 10^9. Then 2 times O(logn) ( for searching and deletion in heap ) would be negligible to O(n)( insertion in sorted array )
1 votes
1 votes

If we implement priority queue using following data structure:

Data Structure Insertion Deletion Search
Linked List O(n) O(1) O(n)
Heap O(logn) O(logn) O(n)
Sorted Array O(n) O(n) O(logn)
Unsorted Array O(1) O(n) O(n)

 

Assuming deletion of max priority element.

So, Heap is the best data structure to implement priority queue.

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
1 answer
2
tishhaagrawal asked Dec 16, 2023
309 views
Below is my approach to solving this question, can anyone please explain if I am doing it the right way?Let X = #free slotssince, m =7 and n = 3So, $4 \leqslant x\leqsla...
0 votes
0 votes
1 answer
4
jugnu1337 asked Oct 22, 2023
333 views
Suppose A is a 12 by 9 incidence matrix from a connected (but unknown) graph with 9 nodes and 12 edges. The diagonal entries of $A^{T}.A$give the number of edges into eac...