Demonstrate how the pseudocode you wrote

Assignment Help Computer Engineering

Reference no: EM132084665

Odds and Ends.

a. Recall that heaps are implemented using arrays. In particular, because heaps make use of complete binary trees, we can label the nodes in a "natural way" using the numbers 1, 2, . . . , n where n is the number of items stored in the heap. If T is the said array, then T[i] contains the item associated with the ith node.

For now, let us assume that T[i].key and T[i].element are respectively the key and element associated with T[i]. We also discussed how to build heaps in a bottom-up fashion.

Assume T[1 · · · n] contains the n items. Below is the pseudocode I presented in class. BuildHeap(v) if v is an external node return else BuildHeap(v.lef tchild) if v.rightchild exists BuildHeap(v.rightchild) endif if v.key < v.lef tchild.key or v.key < v.rightchild.key DownHeapBubble(v) endif endif If we run BuildHeap(T.root) then T[1 · · · n] should be a heap at the end of the algorithm.

a1. Rewrite the above pseudocode so that it takes into account that T is actually an array. That is, instead of v, v.lef tchild and v.rightchild, the pseudocode should refer to the appropriate indices in T. Furthermore, write a procedure for DownHeapBubblev that also takes into account that T is an array.

a2. Demonstrate how the pseudocode you wrote in part (a) for BuildHeap(T.root) runs on the array T[1 · · · 9] whose keys are [22, 15, 36, 44, 10, 3, 9, 13, 29]. That is, show what happens to the array as you make each call to BuildHeap. 1

b. We said that a binary search tree is a binary tree that stores (key, element) pairs at its nodes. It satisfies the property that for every node v, v.key is greater than or equal to every key stored at v's left subtree and v.key is greater than or equal to every key stored at v's right subtree. I noted that this property cannot be weakened to for every node v, v.key = v.lef tchild.key and v.key = v.rightchild.key.

Convince yourself that what I said is indeed true. That is, create a binary tree that stores some (key, element) pairs and satisfies the weakened version of the property but is not a binary search tree.

Reference no: EM132084665

Questions Cloud

Should the two systems be run in parallel : Should it a direct cut over deployment be attempted? It is the cheapest and most direct? Should the two systems be run in parallel?

Write a program in python that requests a user to enter : Write a program in Python that requests a user to enter: percentage of students who received higher than 90 points.

Write a program that will accept two days of the same year : One of the most frustrating aspects of using the Gregorian calendar is that it is difficult to communicate compute elapsed time.

Status of mathematics in the greek conception of science : What was the status of mathematics in the Greek conception of science? In what ways has the Greek conception been preserved, and in what ways has it changed?

Demonstrate how the pseudocode you wrote : Rewrite the above pseudocode so that it takes into account that T is actually an array.

Challenges of the reformation : Did Catholicism mainly benefit from "grassroots" beliefs and practices or because of official responses to the challenges of the Reformation, such as the Counci

How do you write an equality operator : Question: How do you write an equality operator (call it =/) that determines if two yearday instances are equal?

Describe a specific example of philosophy : Renaissance humanism was a philosophy that developed in the 1400s and 1500s in Italy, and then spread throughout Europe. It was a distinct shift away

How to decode or interpret the help documentation : Describe hear briefly the information you found. Submit a screen shot of the help page that described how to avoid this error in the future.

User Account

All Pages