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
25
/ \
/ \
/ \
33 40
/ \ / \
60 75 42 46
/ \
80 65
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
40
/ \
/ \
/ \
60 42
/ \ / \
65 75 80 46
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.
log2(n)
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?
A destructor recovers resources owned by an object. Typically, it deletes memory that the object owns, but that is physically outside the object.
The destructor for class River is called ~River.
The destructor is called any time an object is destroyed, for any reason.
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?
Classes
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?
Programmers are not perfect, and often make mistakes. Also, not all programmers in a team have equal abilities. Classes give someone confidence that everyone on a team has necessarily avoided certain kinds of mistakes. It means you can modify a module and know, for certain, that your modifications do not affect other modules, including modules that were written by other people, and that you have never seen.
(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.
class Rational
{
public:
Rational(int num, int denom);
void flip();
void multiplyBy(const Rational& r);
int getNumerator();
int getDenominator();
private:
int numerator, denominator;
void reduce();
};
Rational::Rational(int num, int denom)
{
numerator = num;
denominator = denom;
reduce();
}
void Rational::flip()
{
int temp = numerator;
numerator = denominator;
denominator = temp;
}
void Rational::multiplyBy(const Rational& r)
{
numerator = numerator * r.numerator;
denonminator = denominator * r.denominator;
}
int Rational::getNumerator()
{
return numerator;
}
int Rational::getDenominator()
{
return denominator;
}
void Rational::reduce()
{
int g = gcd(numerator, denominator);
numerator = numerator / g;
denominator = denominator / g;
}
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".)
int main()
{
Rational x(1,3);
Rational y(3/7);
x.multiplyBy(y);
printf("%i/%i\n", x.getNumerator(), x.getDenominator());
return 0;
}