A)At which positions of a heap might the third smallest key be stored, root? Lef

Question

A)At which positions of a heap might the third smallest key be stored, root? Leftchild or rightChild of a root or some other node?

B)If a priority queue is implemented by an array-based sorted list, where (front, end or any position in the middle of the array) do you want to put the element whose priority is the highest, why? Where (front, end or any position in the middle of the array) do you want to put the element whose priority is the highest if the sorted list is implemented based on SinglyLinkedList, why?

Explanation / Answer

A) In case of binary min heap, the smallest element is always the root element and the element which is just greater  than it i.e. second smallest is placed at it's left and the element which is third smallest and greater than the left node is placed at the right node.So, the third smallest element will be the right child of the root.

B) If the priority queue is implemented by an array-based sorted list, since we know queue is a First in first out data structure and in case of priority queue, the priority is associated with a particular element and the element with the highest priority is dequeued first and the priority of sorted array need not be necessarily in order , but we would want the element with highest priority should be last element, so it is dequeued first, there is no need to move any subsequent items one position back. However, had the element with highest priority be at first position, after dequeuing/poping that all the subsequent elements needs to change its position.

However, in case of sorted singly linked list, it doesn't matter whether we keep element with highest priority first, in the middle or last.

say we have a sorted array List :-

Start node has the address of 3 , 3's address node has address of 5, 5 has the address of 6, 6 has the address of 9 and 9 has address of 11 and 11 has X or end node address.

Let's say the priority of 3rd node is highest, so it will be popped first, when this happens, the only change that will occur is start node will now have the address of 5.

End

Here, 11 will be dequeued followed by adding the X or End node's address in 9's address node

End

Let's say 6 has the highest priority, it is dequeued followed by replacing the 5's address node with 9 rather than 6.

End

All the above 3 operations will lead to change in one address node only, so for sorted linked list it doesn't matter priority element is first, last or middle.

Hope this will help!! Thanks!!! Do give it a thumbs up!!!

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.