Algorithm:
1.) Take and auxillary array of size temp[2N].
2.) Copy elements of first binary heap into temp array from 0 to N-1 then copy elemenst of second binary heap into temp array from N to 2N-1.
3.) Now this temp array should also follow the heap property. So we will build a min-heap of all merged elements together.
----------------------------------------------------------------
Time Complexity:
Copying elements of binary min-heaps into temp array will take time = O(N + N) = O(N)
According to properties of heap data structures building a min or max heap it's worst case time complexity is O(N).
In this way, time complexity to merge two binary min-heaps will be O(N).
Describe the most time-efficient way to implement the operations listed below. Assume no duplicate values and...
In class, we discussed the priority queue (PQ) ADT implemented using min-heap. In a min-heap, the element of the heap with the smallest key is the root of the binary tree. On the other hand, a max-heap has as root the element with the biggest key, and the relationship between the keys of a node and its parent is reversed of that of a min-heap. We also discussed an array-based implementation of heaps. In this assignment, your task is to...
I've posted 3 classes after the instruction that were given at start You will implement and test a PriorityQueue class, where the items of the priority queue are stored on a linked list. The material from Ch1 ~ 8 of the textbook can help you tremendously. You can get a lot of good information about implementing this assignment from chapter 8. There are couple notes about this assignment. 1. Using structure Node with a pointer point to Node structure to...