Suppose that you insert 33 into the following heap. What does the heap look like after the insertion, and after restoring it to a heap using reheapUp? Note that only the priorities are shown. Do not worry about additional information.
25
/ \
/ \
/ \
60 40
/ \ / \
65 75 42 46
/
80
Suppose that you remove the smallest value from the following heap. What does the heap look like after the removal, and after restoring it to a heap using reheapDown?
25
/ \
/ \
/ \
60 40
/ \ / \
65 75 42 46
/
80
How long does it take, in terms of n, to remove the smallest thing from a heap? The answer only needs to be correct to within a constant factor.
What is the purpose of a destructor for a class? What is the destructor for class River called? Under what circumstances is the destructor called?
Object-oriented programming in C++ can be used to make it impossible to violate the abstraction of an abstract data type.
What feature of C++ makes this possible?
Programmers rarely deliberately sabotage their own work. Since programmers are not supposed to violate abstractions, why is it so important that a compiler prevent them from doing so? Can't programmers police themselves?
(This is similar to a problem for quiz 3. This one has you write a class, using object-oriented programming.) A rational number can be represented by a pair of integers, the numerator and the denominator. For example, the rational number with numerator 1 and denominator 3 stands for 1/3. The advantage is that some numbers that can only be represented approximately using type double can be represented exactly as ratios of integers.
An abstract data type Rational is intended to represent rational numbers. So a member of type Rational is thought of as having a numerator and a denominator. Among the operations are a constructor that takes two integers (a numerator and a denominator) and initializes a rational number; an operation flip so that x.flip() makes x into its reciprocal; an operation multiplyBy so that x.multiplyBy(y) makes x into the product of x's current value and y, where y is a rational number; an operation getNumerator that returns the numerator, and an operation getDenominator that returns the denominator. (So x.getNumerator() is the numerator of x.)
Rational numbers are always stored in a form where the numerator and denominator have no common factors. Instead of 3/6, you store 1/2. You cannot assume that somebody who uses this data type knows this convention. There is nothing wrong with creating a rational number with numerator 3 and denominator 6. But it you then ask for the numerator, it will be 1, not 3. This can be achieved by dividing the numerator and denominator by their greatest common divisor. Assume the function gcd(m,n) is available to you. You do not need to write it.
Write Rational in C++ as a class, including the constructor and methods flip, multiplyBy, getNumerator and getDenominator. Also provide a private method called reduce that reduces a rational number by dividing the numerator and denominator by their greatest common divisor. You will want to use reduce in some other functions. All of your functions must be part of the class.
Write a main program that creates rational numbers 1/3 and 3/7, calculates the product of those two numbers, and prints the product in the form numerator/denominator. (So it will print "1/7".)