2 votes

Which of the following data structure is efficient to implement priority queue such as insertion ,deletion, searching?

A)Linked List

B)Heap

C)Sorted Array

D)Unsorted Array

How priority queue can work more efficiently in any data structure, other than heap?

0

i think Heap is generally preferred for priority queue implementation . it gives better performance other thamn linked list and array.

0

**IN Array:**

**1. ARRAY: **

** i) ** insert operation can be implemented by adding an item at end of array in O(1) time .

ii) getHighestPriority operation can be implemented by linearly searching the highest priority item in array. This operation takes O(n) time.

iii) deleteHighestPriority operation can be implemented by first linearly searching an item, then removing the item by moving all subsequent items one position back.

**2.Linked List: **

** **time complexity of all operations with linked list remains same as array. The advantage with linked list is deleteHighestPriority can be more efficient as we don’t have to move items.

**3.Heap:**

** ** i)In a Binary Heap, getHighestPriority can be implemented in O(1) time, insert() can be implemented in O(Logn) time and deleteHighestPriority can also be implemented in O(Logn) time.

ii) fibanooci heap insert() and getHighestPriority can be implemented in O(1) amortized time and deleteHighestPriority can be implemented in O(Logn) amortized time.

Hence Heap is generally preferred for priority queue implementation .

0

I think it is because in sorted array, we can do insertion , deletion, searching in $O\left ( logn \right )$ time.

but heap need build heap method which is $O(n)$ time

but heap need build heap method which is $O(n)$ time

1 vote

Extract from Narsimha Karumanchi which must have made things clear, Someone on Stack Overflow said "Get an algorithms textbook, it is better than random SO questions"

Refer this link @srestha Ma'am , Also sorted array isn't better than heap because logn is much much smaller than n, and also because there are equally large number of insertions, Delete Max and Finds (And 2logn is still way smaller than n)

http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html

https://en.wikipedia.org/wiki/Priority_queue#Implementation

@srestha ma'am If you first refer Narsimha book, you'll get better explanations and also the right concept, @Gateasp2020 refer textbooks instead of online links (I guess you are not doing so and trust me books are much better ), @yajush mishra first understand the context of the question then answer.

Hope I don't offend anyone, just giving honest advice not criticizing anyone.

0

have you read my above comment on the question?

Sorry for not addressing your main question:

How priority queue can work more efficiently in any data structure, other than heap?

@srestha maam please read this:

**First off, How can you deduce this? It is wrong to say anything without workload or number and type of operations we're going to perform, we can only say things, in general case (In priority queues we need to find and extract min or top priority element and since it's a queue there will be a decent number of insertions and deletions so we need an implementation which performs decently on these three operations) **

Now which data structure to choose?

Sorted Array:

As I earlier mentioned if we insert an element in somewhere middle we need to shift remaining elements so takes O(n) time, deletion and search are always for top priority element so O(1).

In case of heaps you know we can find top priority element in O(1) as it's root element, for deleting and inserting elements we need to call heapify which takes O(logn) time.

Unsorted Array: Deletion requires O(n) time as element can be anywhere in middle thus require shifting, insertion can be done anywhere, linear search for find.

0

that means in deletion elements gets priority, which will deleted first

But in case of insertion, there is no priority where to be inserted

Why So?

In priority queue , insertion is like normal array?

1

Normal Deletion (any random element whose value is given) will take O(logn) time but if you are doing normal Deletion and normal search then why do you need "Priority Queue", It can be seen with example of ready queue of processes, we need to extract shortest job (highest priority) everytime, but new incoming jobs can have any burst time, so insertion is done without seeing which elements are already there or considering priority stuff, but when we extract we need highest priority process. Thus operations of priority queue are find max, extract max or Delete max .

0

yes, but our main concern is to know how priority queue work more efficiently in sorted array than heap

In case of insertion deletion searching

Sorted array takes-$O\left ( n \right )+O(1)+O(logn)$

In heap it takes-$O( logn)+O(logn)+O(n)$

So, checking total complexity, we can say sorted arrayis more efficient

right?

0

@srestha maam, what are Priority queue operations?

**1)Insert, Delete and Find** ?

or

**2)Insert, find-min,delete-min** ?

Also, check out the links that I've added in answer.

0

why we need to find min element only, we can find anything and also it maynot have any priority too

Then why find-min operation?

It will be just a find operation

is it not?

0

@Anuj Mishra Narsimha book has a lot of errors. It is useful to get placement questions -- not for learning concepts. If you say you follow this book for algorithms in any IIT interviews there is a high chance you won't be selected. But many IIT people follow this for placements.

0

Thank you Sir, I'll keep this in Mind, I didn't knew about errors, I've used it for practicing problems during gate preparation , luckily I'm following cormen because I wanted to see proof of correctness for algorithms, Now I'll see cormen exercises too

0

I checked cormen

But they mention priority queue as heap structure. Nothing mentioned about sorted array.

right?

Narashima book mentioned time complexity

But not mentioned which one better in performance.

@Arjun Sir

Can u point out, why sorted array is better in performance than heap , in case of priority queue?

1

For this question you do not need any book. The given answer is the best for the asked question. And your doubts are also genuine for the asked question. I'll answer this once I finish answering better questions here.

0

Where is it mentioned that sorted array is better to implement priority queue, everywhere I read it is mentioned that Heaps are used. Can you provide justification to how you come to this conclusion that sorted array is better here?

1

The question asks for "Priority Queue" - assume minimum value is maximum priority. Now, if we use a min-heap we get $O(\log n)$ insertion and deletion. Here, deletion is mostly done for maximum priority (extract-min) and rarely for minimum priority or other values (can be even ignored as they do not consititute necessary priority queue functions). Find is also for maximum priority and can be done in $O(1).$

Now, if we use a sorted array, find will be $O(1)$ -- we search for maximum priority which should be the first value.

Insert will be $O(n)$ because we might need to shift all $n$ elements even if we can find the position in $O(\log n)$ time like in Insertion Sort.

Deletion will be $O(n)$ as we need to shift $n-1$ elements one place.

Min. heap clearly wins rt?

Now, if we use a sorted array, find will be $O(1)$ -- we search for maximum priority which should be the first value.

Insert will be $O(n)$ because we might need to shift all $n$ elements even if we can find the position in $O(\log n)$ time like in Insertion Sort.

Deletion will be $O(n)$ as we need to shift $n-1$ elements one place.

Min. heap clearly wins rt?

0 votes

linked list heap sorted array unsorted array

insertion O(N) O(log N) O(N) O(1)

deletion O(N) O(log N) O(N) O(N)

searching O(N) O(N) O(log N) O(N)

judging by this, I have two main contenders heap and unsorted array. If more insertions than deletion then i will pick unsorted array but in general heap should be the answer so option **B**

0 votes

Heap is generally preferred for priority queue implementation because heaps provide better performance compared arrays or linked list. In a Binary Heap, getHighestPriority() can be implemented in O(1) time, insert() can be implemented in O(Logn) time and deleteHighestPriority() can also be implemented in O(Logn) time.

B is correct option

for good read

https://www.geeksforgeeks.org/priority-queue-set-1-introduction/