A mergable Heap supports the following operations :makeheap(which creates an emp
ID: 3609810 • Letter: A
Question
A mergable Heap supports the following operations :makeheap(which creates an empty mergeableheap),insert,minimum,extract-min and unionShow how to implementmergable heaps using linked lists in each of the followingcases.Analyze the running time of each operation in terms of sizeof the dynamic set being operated on. a.lists are sorted b.lists are unsorted c.lists are unsorted and dynamic sets to be merged aredisjoint. i need to do this as a programming assignment. i also need toadd a testing program that is implementation-independent, i.e., anapplication that uses a mergeable heap without knowing theimplementation for the three implementations stated in theproblem.A mergable Heap supports the following operations :makeheap(which creates an empty mergeableheap),insert,minimum,extract-min and unionShow how to implementmergable heaps using linked lists in each of the followingcases.Analyze the running time of each operation in terms of sizeof the dynamic set being operated on. a.lists are sorted b.lists are unsorted c.lists are unsorted and dynamic sets to be merged aredisjoint. i need to do this as a programming assignment. i also need toadd a testing program that is implementation-independent, i.e., anapplication that uses a mergeable heap without knowing theimplementation for the three implementations stated in theproblem.
Explanation / Answer
{
X <- head[L]
// run insertion sort on the list
}
Insert( )
{
X <- next[nil[L]]
While x != nil [L] and key[x] != k
Do x <- next[x]
// insert x here
}
Minimum( )
{
X <- head[L]
Return x;
}
Extract-Min( )
{
X <- head[L]
List-Delete (L, x);
Return x;
}
Unionshow( )
{
X1 <- head[L]
X2 <- head[L2]
// loop through both lists, comparing the values and insertingthe lesser value into
// newList until one of the lists is empty, then appendremaining elements in non-empty
// list
L = newList;
b)
Make-Heap ( )
{
// do nothing; list is unsorted and has no property tomaintain
}
Insert ( )
{
// search list for repeats. If none exist, insert element athead as follows
next[x] <- head[L]
if head[L] != Nil
then prev[head[L]] <- x
head[L] <- x
prev[x] <- Nil
}
Minimum( )
{
Min = Max_Num
// traverse list in order, comparing values and updating min
return min
}
Extract-Min( )
{
Min = Minimum
// traverse list until match is found, then delete
}
Unionshow ( )
{
// for each element of the other list, sequentially search thislist to see if the element
// already exists. If not, add to the head of this list. If so,quite searching and move on
// to the next element
}
c)
Make-Heap ( )
{
// do nothing; list is unsorted and has no property tomaintain
}
Insert ( )
{
// search list for repeats. If none exist, insert element athead as follows
next[x] <- head[L]
if head[L] != Nil
then prev[head[L]] <- x
head[L] <- x
prev[x] <- Nil
}
Minimum( )
{
Min = Max_Num
// traverse list in order, comparing values and updating min
return min
}
Extract-Min( )
{
Min = Minimum
// traverse list until match is found, then delete
}
Unionshow( ){
// tack the list to be merged onto the end of this list;ordering doesn’t matter and we
// know that there are no repeats to check for
}
Analysis:
a) Lists are sorted.
Make-Heap – theta(n^2) since each of the n elements mustbe compared to, on average, n/2 other elements before their orderedposition is found.
Insert – on average, n/2 elements will have to be checkedbefore the correct spot for insertion is found, and then theinsertion will happen in constant time. The running time istheta(n).
Minimum - since the minimum is, by definition, the first elementin the list, the happens in O(1) time.
Extract-Min – the element to be deleted is the firstelement. The running time is the time to return and delete theelement, which is O(1)
Unionshow – assuming n is the length of this list and m isthe length of the list to be merged, the running time is theta (n +m) since there is at most one comparison for each element.
b) Lists are unsorted.
Make-Heap – no time; nothing needs to be done
Insert – theta (n ) because the list has to be searchedfor repeats before an element can be inserted. Insertion is O(1)since the element can simply be inserted at the head
Minimum – theta(n) because the entire list must besearched to find the minimum
Extract-Min – theta(n) because the entire list must besearched to find the minimum and then the extraction happens inO(1) time.
Unionshow – assuming n is the length of this list and m isthe length of the list to be merged, the running time is theta(m *n) since there entire list must be searched for repeats for eachelement in the second list.
c) Lists are unsorted, and dynamic sets to be merged aredisjoint.
Make-Heap – no time; nothing needs to be done
Insert – theta (n ) because the list has to be searchedfor repeats before an element can be inserted. Insertion is O(1)since the element can simply be inserted at the head
Minimum – theta(n) because the entire list must besearched to find the minimum
Extract-Min – theta(n) because the entire list must besearched to find the minimum and then the extraction happens inO(1) time.
Unionshow – depends on how long it takes to append thelists together, but most likely O(1) since no searching needs to bedone.
I hope this will helps to you