Analysis of algorithm help Heaps with links In class we show

Analysis of algorithm help

Heaps with links In class we showed how heaps can be implemented using an array. In this problem we consider using an implementation using pointers. Consider storing a heap as a linked binary tree with pointers. Give pseudocode on how you would store a heap node, and which modifications you need to make to the heap routines that we discussed in class. What are the runtimes of the heap routines? Now consider storing a heap as a linked list with pointers. Give pseudo-code on how you would store a heap node, and which modifications you need to make to the heap routines that we discussed in class. What are the runtimes of the heap routines? Which of the three heap implementations (array, linked tree, linked list) is preferable? Assume you are given two heaps of height h each, that are given as linked binary trees. And assume we do not require that the last level of the heap is \"flushed left\", i.e., keys can be in any place in the last level. Give an efficient algorithm that merges those two heaps into one heap (without the \"flushed left\" condition). Analyze the runtime of your algorithm.

Solution

(a) The storing of heap as a linked binary tree with pointers requires parent pointer,

1. The pointer to the last node is maintained.

2. From the last node navigate till the new last node is to be inserted,

3. To Remove the node start from the last node and navigate till the second last node , the last node present will be removed .

The pseudocode requires to O(log(n)) time O(1) space for navigation.

(b) . To store the heap as linked list using pointers ,

1. Create a node which is pointed as the first real node of the linked list.

2. Add a node at the front of the linked list .

3. Take a node as the key node to search through the list and returs the pointer corresponding to the search.

4. Remove the node given by the key.

5. Traverse the linked list .

The runtime of the heap by using linked list is O(n) .

(c). The most preferrable way of implementing a heap is by using an array , because it does not requires pointers and thus low memory usage , it is easier to allocate an object and heap is closely managed .

(d). The algorithm to merge two binary tree heaps of same height is,

Node * Heap::merge(Node * n1, Pair * n2)

{

Node *t1, *t2; if (n1==NULL) return n2;

if (n2==NULL) return n1;

if (n1->pri < n2->pri) { t1 = n1; t2 = n2;

} else {t1 = n2; t2 = n1;

} Node * temp = t1->right; t1->right = t1->left; t1->left = merge(temp, t2);

return t1 ;

}

The runtime required by the merge algorithm is O(log(n))