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:
Question
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:
Solution
The level-order traversal of the heap after the insertion of the elements "1" and "7" would be:
Step 1: Insert "1" The elements are inserted from left to right. After inserting "1", the heap would look like this: 10, 8, 5, 3, 2, 1. But since "1" is less than its parent "5", there is no need to heapify.
Step 2: Insert "7" After inserting "7", the heap would look like this: 10, 8, 5, 3, 2, 1, 7. Now, since "7" is greater than its parent "5", we need to swap "7" and "5". The heap now looks like this: 10, 8, 7, 3, 2, 1, 5.
Step 3: Heapify Since "7" is still greater than its new parent "8", we need to swap "7" and "8". The heap now looks like this: 10, 7, 8, 3, 2, 1, 5.
Finally, since "7" is less than its new parent "10", we stop here. The final level-order traversal of the heap after the insertion of the elements "1" and "7" is: 10, 7, 8, 3, 2, 1, 5.
Similar Questions
A priority queue is implemented as a max-heap initially, it has five elements. The level-order traversal of theheap is as follows: 20, 18, 15, 13, 12. Suppose two new elements ‘10’ and ‘17’ are inserted in the heap inthat order. Find the level-order traversal of the heap after the insertion of the element.
Heap can be used as :a) Priority queueb) Stackc) A decreasing order arrayd) None of the mentioned
We discussed an implementation of a min priority queue as a min heap, which had two key properties.1. The min heap property: the key at a node is at most the keys of its children.2. The heap is represented by a complete binary tree.What is the purpose of the complete binary tree property? Select all that apply.It ensures that the minimum key is at the root of the tree.It allows a simple representation of the tree by a vector in a memory efficient manner.It permits us to tell if a given key is contained in the heap in time 𝑂(log𝑛)O(logn).When the heap has 𝑛n elements it insures that the height of the tree is at most log𝑛logn, which in turn means push and pop can be done in time 𝑂(log𝑛)O(logn).Submit
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
In a linked list implementation of a priority queue, how is the order of elements determined?
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.