Question

In: Computer Science

1.Instead of Build-Max-Heap, we could use Heap-Insert-Max to build a tree with heap property. Write a...

1.Instead of Build-Max-Heap, we could use Heap-Insert-Max to build a tree with heap property. Write a pseudocode for that procedure, also evaluate it’s time complexity.
2. How Insertion sort works on the following array
[16, 12, 3, 27, 9, 4, 5, 7]]

Expert Solution

1)

Heap-Insert-Max(A, key)// A is the Max-Heap (array) and key is the value that is being inserted

{

A.size = A.size + 1;

i = A.size;

A[A.size] = key;

while(i > 0 and A[i] > A[Parent(i)])// Parent(i) returns the index of the parent node of node i ( celling(i /2) - 1, assuming array index strats from 0)

{

swap(A[i], A[Parent(i)]);

i = Parent(i);

}

The time compexity for the above pseudo code will be O(logn), where n is the number of nodes present in the Max-Heap. Basically in worst case the inserted node's value may have to traverse up to the root, which is nothing but the hegiht of the binary tree.

2) Insertion Sort works similarly like playing cards, we insert no.s one by one and keep on arranging them unitill all the elements have been inserted and eventually being sorted.

step i [12, 16, 3, 27, 9, 4, 5, 7] <12 is inseretd and compared with 16 as only one precceding data that is 16>

step ii [3, 12, 16, 27, 9, 4, 5, 7] <3 is inseretd and compared with two preceeeeding data 12, 16>

step iii [3, 12, 16, 27, 9, 4, 5, 7] <27 inserted and compared with 16 which is lesser than the inserted data so no further checking required.>

step iv [3, 9, 12, 16, 27, 4, 5, 7] <9 inserted....>

step v [3, 4, 9, 12, 16, 27, 5, 7] <4 inserted.....>

step vi [3, 4, 5, 9, 12, 16, 27, 7] <5 inserted....>

step vii [3, 4, 5, 7, 9, 12, 16, 27] <Finally, 7 inserted and compared with 27, 16, 12, 9, 5 and inserted or placed after 5>

venereology answered 2 hours ago

We can build a heap by repeatedly calling the insert function to insert the elements into...

We can build a heap by repeatedly calling the insert function to insert the elements into the heap. Here is pseudocode: buildHeap(A) h = new empty heap for each element e in A h.insert(e) What is the Big-O runtime of this version of buildHeap? Justify your answer.

In building a regression tree, instead of the mean we can use the median, and instead...

In building a regression tree, instead of the mean we can use the median, and instead of minimizing the squared error we can minimize the absolute error. Why does this help in the case of noise?

Language C++ Implement a Priority Queue with a Binary HEAP. Use a Max Heap. Create a...

Language C++ Implement a Priority Queue with a Binary HEAP. Use a Max Heap. Create a class called Node: Have a Name and Priority.Data set - 10 is the highest priority, 1 is lowest priority. Enqueue and dequeue in the following order. Function Name, Priority Enqueue Joe, 3 Enqueue Fred,1 Enqueue Tuyet,9 Enqueue Jose, 6 Dequeue Enqueue Jing, 2 Enqueue Xi, 5 Enqueue Moe, 3 DequeueEnqueue Miko, 7 Enqueue Vlady, 8 Enqueue Frank, 9 Enqueue Anny, 3 DequeueEnqueue Xi, 2 Enqueue Wali, 2 Enqueue xChe, 6 Enqueue xVerra, 8 Dequeue Dequeue Dequeue Dequeue...

Build a Max Heap using the following: A= {20, 15, 10, 14, 8, 6, 9}

Write a non recursive method to insert into an AVL tree in Java

This problem requires you to use a heap to store items, but instead of using a...

This problem requires you to use a heap to store items, but instead of using a key of an item to determine where to store the item in the heap, you need to assign a priority (key) to each item that will determine where it is inserted in the heap a) Show how to assign priorities to items to implement a first-in, first-out queue with a heap. b) Show how to assign priorities to items to implement a first-in, last-out...

This problem requires you to use a heap to store items, but instead of using a key of an item to determine where to store the item in the heap

This problem requires you to use a heap to store items, but instead of using a key of an item to determine where to store the item in the heap, you need to assign a priority (key) to each item that will determine where it is inserted in the heap 7a) Show how to assign priorities to items to implement a first-in, first-out queue with a heap. 7b) Show how to assign priorities to items to implement a first-in, last-out stack with...

Insert VTQWDNGOCMKPI into a 2-3 tree (A B-Tree with Min set to 1) in the given...

Insert VTQWDNGOCMKPI into a 2-3 tree (A B-Tree with Min set to 1) in the given order and show the result at each step. Then, delete WKN in the given order and show result at each step

1) In this experiment, we purified cyclohexene by distillation. Could we have used recrystallization instead to...

1) In this experiment, we purified cyclohexene by distillation. Could we have used recrystallization instead to purify? Explain. 2) At the end we stopped the distillation with some material left in the vial. Why is it considered unsafe to distill until dryness? please help!

In MobaXterm, with the use of the binary search tree. Implement four operations of insert, in-order...

In MobaXterm, with the use of the binary search tree. Implement four operations of insert, in-order traversal, preorder traversal, and find. Please separate the code in the four parts and explain in detail what is happening. Also, if you can please basic C language. If not, then I understand. Thank you for your time. The test cases are 'm', 'd', 'g', 'r', 'p', 'b', and 'x'. Output: Enter choice (lower case is also acceptable) --- (I)nsert, (F)ind, (Q)uit: i Enter...