Made Easy Test Series:Programming and DS

Question

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?

Comments

In sorted array for deletion and insertion, we have to perform shifting which takes O(n) time

---

@Anuj Mishra

I yesterday saw somewhere, deletion will take O(1) time. As because, there is certain priority on elements of queue

---

It will be called Extract-Min then which will extract the top element. That way we can do in O(1) time. I guess you're right we delete only max element but what about insertion, that can't be done in O(1) it will take O(n) for shifting also array will need to have dynamic size.

Answer 1

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.

Comments

@Anuj Mishra

u just copy-paste the answer. Can u explain the concept a bit?

---

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.

---

@Anuj Mishra

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?

---

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 .

---

@Anuj Mishra

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?

---

@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.

---

@Anuj Mishra

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?

---

In SO they would have meant a standard book like Cormen 😄

---

which line of cormen?

---

@Arjun sir you're right cormen is better, but It doesn't have such comparison between different implementations of priority queue as is done in Narsimha book,

@srestha ma'am, 3rd edition chapter 6 -Chapter notes(For future reference just do ctrl+F in PDF version)

---

@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.

---

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

---

@Anuj Mishra

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?

---

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.

---

ok :)
is that mean heap can be answer too?

---

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?

---

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?

Answer 2

                                   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

Comments

no, I donot think it is correct

because sorted array insertion deletion cannot be $O(n)$

---

and also tell me how priority queue operating on sorted array

Answer 3

Answer is heap because heap takes minimum time in Enqueue and Dequeue as O(logn)

Answer 4

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/