Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS430 Assignment 2

2022

Ethics: Any behavior on any homework or exam that could be considered copying or cheating will result in an immediate zero on the assignment

involved

You can use either English or pseudo-code in questions that need you to present your algorithms . If you use pseudo- code, make sure that each line is numbers, make sure that the indentation is correct, and clarify that your arrays        have either index 1 to  or 0 to  − 1.

1.     Provide pseudo-code for the operation MAX-HEAP-DELETE ( , ) that deletes the element in [] from a   binary max-heap  . In your code, you can call MAX-HEAPIFY from the textbook/lecture notes directly if you want to. Analyze the running time of your algorithm.

2.    A  -ary heap is like a binary heap, but each non-leaf node has at most  children instead of 2, and the data structure is on a complete  -ary tree.

a.     How to represent a  -ary heap in an array? (You want to answer these following questions: Where do we put each element into the array? How to find the parent of a node? And how to find the  ℎ  child of a        node?)

b.     How to MAX-HEAPIFY ( , ) in a  -ary max-heap? Analyze its running time in terms of  and  .

c.     Present an efficient implementation of INCREASE-KEY ( ,  , ) and INSERT ( , ) in a  -ary max-heap. Analyze their time complexity in terms of  and  .

3.     Present an algorithm that returns the largest  elements in a binary max-heap with  elements in O( lg )  time. Here,  can be some number that is much smaller than  , so your algorithm should not depend on the size of the heap .

Hint: you need to consider who are the candidates for the  ℎ  largest element. It is easy to see that the root      contains the only candidate for the 1 largest element, then who are the candidates for the 2 largest             element after the 1 largest element is determined? Who are the candidates for the 3 largest element after the 2 largest element is determined? And so on . Eventually, you will find that there are  candidates for the    ℎ  largest element after the ( − 1)ℎ  largest element is determined . Next, you need to consider how to use    another data structure to maintain these candidates.

4.     Show that if a node in a binary search tree has two children, then its successor has no left child, and its predecessor has no right child .