A priority queue is implemented as a max-heap initially, it has five elements. The level-order traversal of the heap is as follows: 20, 18, 15, 13, 12. Suppose two new elements ‘10’ and ‘17’ are inserted in the heap in that order. Find the level-order traversal of the heap after the insertion of the element.
Question
A priority queue is implemented as a max-heap initially, it has five elements. The level-order traversal of the heap is as follows: 20, 18, 15, 13, 12. Suppose two new elements ‘10’ and ‘17’ are inserted in the heap in that order. Find the level-order traversal of the heap after the insertion of the element.
Solution
The level-order traversal of a max-heap is done by visiting each level of the heap from left to right, starting from the root.
The initial heap is: 20, 18, 15, 13, 12.
When we insert '10', it goes to the next available spot in the level order, which is after '12'. But '10' is less than its parent '18', so it stays at the same spot. The heap becomes: 20, 18, 15, 13, 12, 10.
Next, we insert '17'. It goes to the next available spot, which is after '10'. But '17' is less than its parent '20' but greater than its sibling '18'. So, we swap '17' and '18'. The heap becomes: 20, 17, 15, 13, 12, 10, 18.
So, the level-order traversal of the heap after the insertion of the elements '10' and '17' is: 20, 17, 15, 13, 12, 10, 18.
Similar Questions
A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Two new elements ”1‘ and ”7‘ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:
n a linked list implementation of a priority queue, how is the order of elements determined?*1 pointElements are randomly orderedElements are sorted by their valuesElements are sorted by their insertion orderElements are sorted by their priorities
How is the priority of an element determined in a priority queue?OptionsBy its insertion orderBy its valueBy its position in the queueBy its frequency of access
Heap can be used as :a) Priority queueb) Stackc) A decreasing order arrayd) None of the mentioned
A priority queue can efficiently implemented using which of the following data structures? Assume that the number of insert and peek (operation to see the current highest priority item) and extraction (remove the highest priority item) operations are almost same.ArrayLinkedListHeap Data Structures like Binary Heap, Fibonacci HeapAll of the above
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.