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

CS430 Assignment 2


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



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 .