text:
The Way of the Java/Queues

Queues and Priority Queues
This chapter presents two ADTs: Queues and Priority Queues. In real life a queue is a line of customers waiting for service of some kind. In most cases, the first customer in line is the next customer to be served. There are exceptions, though. For example, at airports customers whose flight is leaving imminently are sometimes taken from the middle of the queue. Also, at supermarkets a polite customer might let someone with only a few items go first.

The rule that determines who goes next is called a queueing discipline. The simplest queueing discipline is called FIFO, for ``first-in-first-out.'' The most general queueing discipline is priority queueing, in which each customer is assigned a priority, and the customer with the highest priority goes first, regardless of the order of arrival. The reason I say this is the most general discipline is that the priority can be based on anything: what time a flight leaves, how many groceries the customer has, or how important the customer is. Of course, not all queueing disciplines are ``fair,'' but fairness is in the eye of the beholder.

The Queue ADT and the Priority Queue ADT have the same set of operations and their interfaces are the same. The difference is in the semantics of the operations: a Queue uses the FIFO policy, and a Priority Queue (as the name suggests) uses the priority queueing policy.

As with most ADTs, there are a number of ways to implement queues. Since a queue is a collection of items, we can use any of the basic mechanisms for storing collections, including arrays and lists. Our choice among them will be based in part on their performance--- how long it takes to perform the operations we want to perform--- and partly on ease of implementation.

The queue ADT
ADT!Queue Queue ADT implementation!Queue queue!List implementation

The queue ADT is defined by the following operations:

description

[constructor:] Create a new, empty queue.

[insert:] Add a new item to the queue.

[remove:] Remove and return an item from the queue. The item that is returned is the first one that was added.

[empty:] Check whether the queue is empty.

description

To demonstrate a queue implementation, I will take advantage of the LinkedList class from Chapter list. Also, I will assume that we have a class named Customer that defines all the information about each customer, and the operations we can perform on customers.

As far as our implementation goes, it does not matter what kind of object is in the Queue, so we can make it generic. Here is what the implementation looks like.

verbatim public class Queue public LinkedList list;

public Queue list = new List ;

public boolean empty return list.empty ;

public void insert (Object obj) list.addLast (obj);

public Object remove return list.removeFirst ;

verbatim

A queue object contains a single instance variable, which is the list that implements it. For each of the other methods, all we have to do is invoke one of the methods from the LinkedList class.

Veneer
veneer performance hazard performance analysis

An implementation like this is called a veneer. In real life, veneer is a thin coating of good quality wood used in furniture-making to hide lower quality wood underneath. Computer scientists use this metaphor to describe a small piece of code that hides the details of an implementation and provides a simpler, or more standard, interface.

This example demonstrates one of the nice things about a veneer, which is that it is easy to implement, and one of the dangers of using a veneer, which is the performance hazard!

Normally when we invoke a method we are not concerned with the details of its implementation. But there is one ``detail'' we might want to know---the performance characteristics of the method. How long does it take, as a function of the number of items in the list?

First let's look at removeFirst.

verbatim public Object removeFirst Object result = head; if (head != null) head = head.next; return result; verbatim

There are no loops or function calls here, so that suggests that the run time of this method is the same every time. Such a method is called a constant time operation. In reality, the method might be slightly faster when the list is empty, since it skips the body of the conditional, but that difference is not significant.

constant time

The performance of addLast is very different.

verbatim public void addLast (Object obj) // special case: empty list if (head == null) head = new Node (obj, null); return; Node last; for (last = head; last.next != null; last = last.next) // traverse the list to find the last node last.next = new Node (obj, null); verbatim

The first conditional handles the special case of adding a new node to an empty list. In this case, again, the run time does not depend on the length of the list. In the general case, though, we have to traverse the list to find the last element so we can make it refer to the new node.

This traversal takes time proportional to the length of the list. Since the run time is a linear function of the length, we would say that this method is linear time. Compared to constant time, that's very bad.

linear time

Linked Queue
queue!linked implementation linked queue

We would like an implementation of the Queue ADT that can perform all operations in constant time. One way to accomplish that is to implement a linked queue, which is similar to a linked list in the sense that it is made up of zero or more linked Node objects. The difference is that the queue maintains a reference to both the first and the last node, as shown in the figure.

figure=figs/queue1.eps,width=4in

Here's what a linked Queue implementation looks like:

verbatim public class Queue public Node first, last;

public Queue first = null; last = null;

public boolean empty return first == null;

verbatim

So far it is straightforward. In an empty queue, both first and last are null. To check whether a list is empty, we only have to check one of them.

insert is a little more complicated because we have to deal with several special cases.

verbatim public void insert (Object obj) Node node = new Node (obj, null); if (last != null) last.next = node; last = node; if (first == null) first = last; verbatim

The first condition checks to make sure that last refers to a node; if it does then we have to make it refer to the new node.

The second condition deals with the special case where the list was initially empty. In this case both first and last refer to the new node.

remove also deals with several special cases.

verbatim public Object remove Node result = first; if (first != null) first = first.next; if (first == null) last = null; return result; verbatim

The first condition checks whether there were any nodes in the queue. If so, we have to copy the next node into first. The second condition deals with the special case that the list is now empty, in which case we have to make last null.

As an exercise, draw diagrams showing both operations in both the normal case and in the special cases, and convince yourself that they are correct.

Clearly, this implementation is more complicated than the veneer implementation, and it is more difficult to demonstrate that it is correct. The advantage is that we have achieved the goal: both insert and remove are constant time.

Circular buffer
queue!circular buffer implementation circular buffer buffer!circular

Another common implementation of a queue is a circular buffer. ``Buffer'' is a general name for a temporary storage location, although it often refers to an array, as it does in this case. What it means to say a buffer is ``circular'' should become clear in a minute.

The implementation of a circular buffer is similar to the array implementation of a stack, as in Section arraystack. The queue items are stored in an array, and we use indices to keep track of where we are in the array. In the stack implementation, there was a single index that pointed to the next available space. In the queue implementation, there are two indices: first points to the space in the array that contains the first customer in line and next points to the next available space.

The following figure shows a queue with two items (represented by dots).

figure=figs/queue2.eps,width=4in

There are two ways to think of the variables first and last. Literally, they are integers, and their values are shown in boxes on the right. Abstractly, though, they are indices of the array, and so they are often drawn as arrows pointing to locations in the array. The arrow representation is convenient, but you should remember that the indices are not references; they are just integers.

Here is an incomplete array implementation of a queue:

verbatim public class Queue public Object[] array; public int first, next;

public Queue array = new Object[128]; first = 0; next = 0;

public boolean empty return first == next; verbatim

The instance variables and the constructor are straightforward, although again we have the problem that we have to choose an arbitrary size for the array. Later we will solve that problem, as we did with the stack, by resizing the array if it gets full.

The implementation of empty is a little surprising. You might have thought that first == 0 would indicate an empty queue, but that neglects the fact that the head of the queue is not necessarily at the beginning of the array. Instead, we know that the queue is empty if head equals next, in which case there are no items left. Once we see the implementation of insert and remove, that situation will make more sense.

verbatim public void insert (Object item) array[next] = item; next++;

public Object remove Object result = array[first]; first++; return result; verbatim

insert looks very much like push in Section arraystack; it puts the new item in the next available space and then increments the index.

remove is similar. It takes the first item from the queue and then increments first so it refers to the new head of the queue. The following figure shows what the queue looks like after both items have been removed.

figure=figs/queue3.eps,width=4in

It is always true that next points to an available space. If first catches up with next and points to the same space, then first is referring to an ``empty'' location, and the queue is empty. I put ``empty'' in quotation marks because it is possible that the location that first points to actually contains a value (we do nothing to ensure that empty locations contain null); on the other hand, since we know the queue is empty, we will never read this location, so we can think of it, abstractly, as empty.

As an exercise, fix remove so that it returns null if the queue is empty.

The next problem with this implementation is that eventually it will run out of space. When we add an item we increment next and when we remove an item we increment first, but we never decrement either. What happens when we get to the end of the array?

The following figure shows the queue after we add four more items:

figure=figs/queue4.eps,width=4in

The array is now full. There is no ``next available space,'' so there is nowhere for next to point. One possibility is that we could resize the array, as we did with the stack implementation. But in that case the array would keep getting bigger regardless of how many items were actually in queue. A better solution is to wrap around to the beginning of the array and reuse the spaces there. This ``wrap around'' is the reason this implementation is called a circular buffer.

One way to wrap the index around is to add a special case whenever we increment an index:

verbatim next++; if (next == array.length) next = 0; verbatim

A fancy alternative is to use the modulus operator:

verbatim next = (next + 1) verbatim

Either way, we have one last problem to solve. How do we know if the queue is really full, meaning that we cannot insert another item? The following figure shows what the queue looks like when it is ``full.''

figure=figs/queue5.eps,width=4in

There is still one empty space in the array, but the queue is full because if we insert another item, then we have to increment next such that next == first, and in that case it would appear that the queue was empty!

To avoid that, we sacrifice one space in the array. So how can we tell if the queue is full?

verbatim if ((next + 1) verbatim

And what should we do if the array is full? In that case resizing the array is probably the only option.

As an exercise, put together all the code from this section and write an implementation of a queue using a circular buffer that resizes itself when necessary.

Priority queue
priority queue!ADT ADT!Priority Queue

The Priority Queue ADT has the same interface as the Queue ADT, but different semantics. The interface is:

description

[constructor:] Create a new, empty queue.

[insert:] Add a new item to the queue.

[remove:] Remove and return an item from the queue. The item that is returned is the one with the highest priority.

[empty:] Check whether the queue is empty.

description

The semantic difference is that the item that is removed from the queue is not necessarily the first one that was added. Rather, it is whatever item in the queue has the highest priority. What the priorities are, and how they compare to each other, are not specified by the Priority Queue implementation. It depends on what the items are that are in the queue.

For example, if the items in the queue have names, we might choose them in alphabetical order. If they are bowling scores, we might choose from highest to lowest, but if they are golf scores, we would go from lowest to highest.

generic data structure!generic

So we face a new problem. We would like an implementation of Priority Queue that is generic---it should work with any kind of object---but at the same time the code that implements Priority Queue needs to have the ability to compare the objects it contains.

We have seen a way to implement generic data structures using Objects, but that does not solve this problem, because there is no way to compare Objects unless we know what type they are.

The answer lies in a new Java feature called an abstract class.

Abstract class
abstract class class!abstract Comparable abstract class!Comparable

An abstract class is a set of classes. The abstract class definition specifies the requirements a class must satisfy to be a member.

Often abstract classes have names that end in ``able'' to indicate the fundamental capability the abstract class requires. For example, any class that provides a method named draw can be a member of the abstract class named Drawable. Any class that contains a method named start can be a member of the abstract class Runnable.

As of Java 2, Java provides a built-in abstract class that we can use in an implementation of a Priority Queue. It is called Comparable, and it means what it says. Any class that belongs to the Comparable abstract class has to provide a method named compareTo that compares two objects and returns a value indicating whether one is larger or smaller than the other, or whether they are the same.

Many of the built-in Java classes are members of the Comparable abstract class, including numeric wrapper classes like Integer and Double.

In the next section I will show how to write an ADT that manipulates an abstract class. Then we will see how to write a new (concrete) class that belongs to an existing abstract class. Then we will see how to write a new abstract class.

Array implementation of Priority Queue
implementation!Priority Queue priority queue!array implementation

In the implementation of the Priority Queue, every time we specify the type of the items in the queue, we specify the abstract class Comparable. For example, the instance variables are an array of Comparables and an integer:

verbatim public class PriorityQueue private Comparable[] array; private int index;

verbatim

As usual, index is the index of the next available location in the array. The instance variables are declared private so that other classes cannot have direct access to them.

The constructor and empty are similar to what we have seen before. I chose the initial size for the array arbitrarily.

verbatim public PriorityQueue array = new Comparable [16]; index = 0;

public boolean empty return index == 0; verbatim

insert is similar to push:

verbatim public void insert (Comparable item) if (index == array.length) resize ; array[index] = item; index++; verbatim

I omitted the implementation of resize. The only substantial method in the class is remove, which has to traverse the array to find and remove the largest item:

verbatim public Comparable remove if (index == 0) return null;

int maxIndex = 0;

// find the index of the item with the highest priority for (int i=1; i 0) maxIndex = i;       Comparable result = array[maxIndex];

// move the last item into the empty slot index--; array[maxIndex] = array[index]; return result; verbatim

As we traverse the array, maxIndex keeps track of the index of the largest element we have seen so far. What it means to be the ``largest'' is determined by compareTo. In this case the compareTo method is provided by the Integer class, and it does what we expect---larger (more positive) numbers win.

A Priority Queue client
client abstract class class!abstract

The implementation of Priority Queue is written entirely in terms of Comparable objects, but there is no such thing as a Comparable object! Go ahead, try to create one:

verbatim Comparable comp = new Comparable ;      // ERROR verbatim

You'll get a compile-time message that says something like ``java.lang.Comparable is an interface. It can't be instantiated.'' In Java, abstract classes are called interfaces. I have avoided this word so far because it also means several other things, but now you have to know.

interface

Why can't abstract classes be instantiated? Because an abstract class only specifies requirements (you must have a compareTo method); it does not provide an implementation.

To create a Comparable object, you have to create one of the objects that belongs to the Comparable set, like Integer. Then you can use that object anywhere a Comparable is called for.

verbatim PriorityQueue pq = new PriorityQueue ; Integer item = new Integer (17); pq.insert (item); verbatim

This code creates a new, empty Priority Queue and a new Integer object. Then it inserts the Integer into the queue. insert is expecting a Comparable as a parameter, so it is perfectly happy to take an Integer. If we try to pass a Rectangle, which does not belong to Comparable, we get a compile-time message like, ``Incompatible type for method. Explicit cast needed to convert java.awt.Rectangle to java.lang.Comparable.''

That's the compiler telling us that if we want to make that conversion, we have to do it explicitly. We might try to do what it says:

verbatim Rectangle rect = new Rectangle ; pq.insert ((Comparable) rect); verbatim

But in that case we get a run-time error, a ClassCastException. When the Rectangle tries to pass as a Comparable, the run-time system checks whether it satisfies the requirements, and rejects it. So that's what we get for following the compiler's advise.

ClassCastException exception!ClassCastException

To get items out of the queue, we have to reverse the process:

verbatim while (!pq.empty ) item = (Integer) pq.remove ; System.out.println (item); verbatim

This loop removes all the items from the queue and prints them. It assumes that the items in the queue are Integers. If they were not, we would get a ClassCastException.

The Golfer class
Golfer class!Golfer abstract class!implementing Comparable

Finally, let's look at how we can make a new class that belongs to Comparable. As an example of something with an unusual definition of ``highest'' priority, we'll use golfers:

verbatim public class Golfer implements Comparable String name; int score;

public Golfer (String name, int score) this.name = name; this.score = score;

verbatim

The class definition and the constructor are pretty much the same as always; the difference is that we have to declare that Golfer implements Comparable. In this case the keyword implements means that Golfer implements the interface specified by Comparable.

If we try to compile Golfer.java at this point, we get something like ``class Golfer must be declared abstract. It does not define int compareTo(java.lang.Object) from interface java.lang.Comparable.'' In other words, to be a Comparable, Golfer has to provide a method named compareTo. So let's write one:

verbatim public int compareTo (Object obj) Golfer that = (Golfer) obj;

int a = this.score; int b = that.score; // for golfers, low is good! if (a < b) return 1; if (a > b) return -1; return 0; verbatim

Two things here are a little surprising. First, the parameter is an Object. That's because in general the caller doesn't know what type the objects are that are being compared. For example, in PriorityQueue.java when we invoke compareTo, we pass a Comparable as a parameter. We don't have to know whether it is an Integer or a Golfer or whatever.

Inside compareTo we have to convert the parameter from an Object to a Golfer. As usual, there is a risk when we do this kind of cast: if we cast to the wrong type we get an exception.

Finally, we can create some golfers:

verbatim Golfer tiger = new Golfer ("Tiger Woods", 61); Golfer phil = new Golfer ("Phil Mickelson", 72); Golfer hal = new Golfer ("Hal Sutton", 69); verbatim

And put them in the queue:

verbatim pq.insert (tiger); pq.insert (phil); pq.insert (hal); verbatim

When we pull them out:

verbatim while (!pq.empty ) golfer = (Golfer) pq.remove ; System.out.println (golfer); verbatim

They appear in descending order (for golfers):

verbatim Tiger Woods    61 Hal Sutton     69 Phil Mickelson 72 verbatim

When we switched from Integers to Golfers, we didn't have to make any changes in PriorityQueue.java at all. So we succeeded in maintaining a barrier between PriorityQueue and the classes that use it, allowing us to reuse the code without modification. Furthermore, we were able to give the client code control over the definition of compareTo, making this implementation of PriorityQueue more versatile.

Glossary
queue queueing discipline FIFO priority queue veneer constant time linear time performance hazard linked queue circular buffer abstract class interface

description

[queue:] An ordered set of objects waiting for a service of some kind.

[queueing discipline:] The rules that determine which member of a queue is removed next.

[FIFO:] ``first in, first out,'' a queueing discipline in which the first member to arrive is the first to be removed.

[priority queue:] A queueing discipline in which each member has a priority determined by external factors. The member with the highest priority is the first to be removed.

[Priority Queue:] An ADT that defines the operations one might perform on a priority queue.

[veneer:] A class definition that implements an ADT with method definitions that are invocations of other methods, sometimes with simple transformations. The veneer does no significant work, but it improves or standardizes the interface seen by the client.

[performance hazard:] A danger associated with a veneer that some of the methods might be implemented inefficiently in a way that is not apparent to the client.

[constant time:] An operation whose run time does not depend on the size of the data structure.

[linear time:] An operation whose run time is a linear function of the size of the data structure.

[linked queue:] An implementation of a queue using a linked list and references to the first and last nodes.

[circular buffer:] An implementation of a queue using an array and indices of the first element and the next available space.

[abstract class:] A set of classes. The abstract class specification lists the requirements a class must satisfy to be included in the set.

[interface:] The Java word for an abstract class. Not to be confused with the more broad meaning of the word interface.

title: The Way of the Java/Queues


text:
The Way of the Java/Trees

Trees
tree ADT data structure

This chapter presents a new data structure called a tree, some of its uses and two ways to implement it.

A possible source of confusion is the distinction between an ADT, a data structure, and an implementation of an ADT or data structure. There is no universal answer, because something that is an ADT at one level might in turn be the implementation of another ADT.

diagram!implementation

To help keep some of this straight, it is sometimes useful to draw a diagram showing the relationship between an ADT and its possible implementations. This figure shows that there are two implementations of a tree:

figure=figs/tree_adt.eps

The horizontal line in the figure represents the barrier of abstraction between the ADT and its implementations.

A tree node
node tree node cargo embedded reference implementation!Tree binary tree

Like lists, trees are made up of nodes. A common kind of tree is a binary tree, in which each node contains a reference to two other nodes (possibly null). The class definition looks like this:

verbatim public class Tree Object cargo; Tree left, right;

verbatim

Like list nodes, tree nodes contain cargo: in this case a generic Object. The other instance variables are named left and right, in accordance with a standard way to represent trees graphically:

figure=figs/tree1.eps

The top of the tree (the node referred to by tree) is called the root. In keeping with the tree metaphor, the other nodes are called branches and the nodes at the tips with null references are called leaves. It may seem odd that we draw the picture with the root at the top and the leaves at the bottom, but that is not the strangest thing.

root node leaf node parent node child node level

To make things worse, computer scientists mix in yet another metaphor: the family tree. The top node is sometimes called a parent and the nodes it refers to are its children. Nodes with the same parent are called siblings, and so on.

Finally, there is also a geometric vocabulary for taking about trees. I already mentioned left and right, but there is also ``up'' (toward the parent/root) and down (toward the children/leaves). Also, all the nodes that are the same distance from the root comprise a level of the tree.

I don't know why we need three metaphors for talking about trees, but there it is.

Building trees
tree!linked implementation

The process of assembling tree nodes is similar to the process of assembling lists. We have a constructor for tree nodes that initializes the instance variables.

verbatim public Tree (Object cargo, Tree left, Tree right) this.cargo = cargo; this.left = left; this.right = right; verbatim

We allocate the child nodes first:

verbatim Tree left = new Tree (new Integer(2), null, null); Tree right = new Tree (new Integer(3), null, null); verbatim

We can create the parent node and link it to the children at the same time:

verbatim Tree tree = new Tree (new Integer(1), left, right); verbatim

This code produces the state shown in the previous figure.

Traversing trees
tree!traversal traverse

The most natural way to traverse a tree is recursively. For example, to add up all the integers in a tree, we could write this class method:

verbatim public static int total (Tree tree) if (tree == null) return 0; Integer cargo = (Integer) tree.cargo; return cargo.intValue + total (tree.left) + total (tree.right); verbatim

This is a class method because we would like to use null to represent the empty tree, and make the empty tree the base case of the recursion. If the tree is empty, the method returns 0. Otherwise it makes two recursive calls to find the total value of its two children. Finally, it adds in its own cargo and returns the total.

tree!empty

Although this method works, there is some difficulty fitting it into an object-oriented design. It should not appear in the Tree class because it requires the cargo to be Integer objects. If we make that assumption in Tree.java then we lose the advantages of a generic data structure.

On the other hand, this code accesses the instance variables of the Tree nodes, so it ``knows'' more than it should about the implementation of the tree. If we changed that implementation later (and we will) this code would break.

Later in this chapter we will develop ways to solve this problem, allowing client code to traverse trees containing any kinds of objects without breaking the abstraction barrier between the client code and the implementation. Before we get there, let's look at an application of trees.

Expression trees
tree!expression expression tree postfix infix

A tree is a natural way to represent the structure of an expression. Unlike other notations, it can represent the compotation unambiguously. For example, the infix expression 1 + 2 * 3 is ambiguous unless we know that the multiplication happens before the addition.

The following figure represents the same computation:

figure=figs/tree2.eps

The nodes can be operands like 1 and 2 or operators like + and *. Operands are leaf nodes; operator nodes contain references to their operands (all of these operators are binary, meaning they have exactly two operands).

Looking at this figure, there is no question what the order of operations is: the multiplication happens first in order to compute the first operand of the addition.

Expression trees like this have many uses. The example we are going to look at is translation from one format (postfix) to another (infix). Similar trees are used inside compilers to parse, optimize and translate programs.

Traversal
tree!traversal traverse recursion preorder postorder inorder

I already pointed out that recursion provides a natural way to traverse a tree. We can print the contents of an expression tree like this:

verbatim public static void print (Tree tree) if (tree == null) return; System.out.print (tree + " "); print (tree.left); print (tree.right); verbatim

In other words, to print a tree, first print the contents of the root, then print the entire left subtree, then print the entire right subtree. This way of traversing a tree is called a preorder, because the contents of the root appear before the contents of the children.

For the example expression the output is + 1 * 2 3. This is different from both postfix and infix; it is a new notation called prefix, in which the operators appear before their operands.

You might suspect that if we traverse the tree in a different order we get the expression in a different notation. For example, if we print the subtrees first, and then the root node:

verbatim public static void printPostorder (Tree tree) if (tree == null) return; printPostorder (tree.left); printPostorder (tree.right); System.out.print (tree + " "); verbatim

We get the expression in postfix (1 2 3 * +)! As the name of the previous method implies, this order of traversal is called postorder. Finally, to traverse a tree inorder, we print the left tree, then the root, then the right tree:

verbatim public static void printInorder (Tree tree) if (tree == null) return; printInorder (tree.left); System.out.print (tree + " "); printInorder (tree.right); verbatim

The result is 1 + 2 * 3, which is the expression in infix.

To be fair, I have to point out that I omitted an important complication. Sometimes when we write an expression in infix we have to use parentheses to preserve the order of operations. So an inorder traversal is not quite sufficient to generate an infix expression.

Nevertheless, with a few improvements, the expression tree and the three recursive traversals provide a general way to translate expressions from one format to another.

Encapsulation
encapsulation client provider abstract class class!abstract

As I mentioned before, there is a problem with the way we have been traversing trees: it breaks down the barrier between the client code (the application that uses the tree) and the provider code (the Tree implementation). Ideally, tree code should be general; it shouldn't know anything about expression trees. And the code that generates and traverses the expression tree shouldn't know about the implementation of the trees. This design criterion is called object encapsulation to distinguish it from the encapsulation we saw in Section encapsulation, which we might call method encapsulation.

In the current version, the Tree code knows too much about the client. Instead, the Tree class should provide the general capability of traversing a tree in various ways. As it traverses, it should perform operations on each node that are specified by the client.

Visitable abstract class!Visitable

To facilitate this separation of interests, we will create a new abstract class, called Visitable. The items stored in a tree will be required to be visitable, which means that they define a method named visit that does whatever the client wants done to each node. That way the Tree can perform the traversal and the client can perform the node operations.

Here are the steps we have to perform to wedge an abstract class between a client and a provider:

enumerate

Define an abstract class that specifies the methods the provider code will need to invoke on its components.

Write the provider code in terms of the new abstract class, as opposed to generic Objects.

Define a concrete class that belongs to the abstract class and that implements the required methods as appropriate for the client.

Write the client code to use the new concrete class.

enumerate

The next few sections demonstrate these steps.

Defining an abstract class
abstract class!defining interface

An abstract class definition looks a lot like a concrete class definition, except that it only specifies the interface of each method and not an implementation. The definition of Visitable is

verbatim public interface Visitable public void visit ;

verbatim

That's it! The word interface is Java's keyword for an abstract class. The definition of visit looks like any other method definition, except that it has no body. This definition specifies that any class that implements Visitable has to have a method named visit that takes no parameters and that returns void.

body!method

Like other class definitions, abstract class definitions go in a file with the same name as the class (in this case Visitable.java).

Implementing an abstract class
abstract class!implementing Token class class!Token

If we are using an expression tree to generate infix, then ``visiting'' a node means printing its contents. Since the contents of an expression tree are tokens, we'll create a new concrete class called Token that implements Visitable

verbatim public class Token implements Visitable String str;

public Token (String str) this.str = str;

public void visit System.out.print (str + " ");

verbatim

When we compile this class definition (which is in a file named Token.java), the compiler checks whether the methods provided satisfy the requirements specified by the abstract class. If not, it will produce an error message. For example, if we misspell the name of the method that is supposed to be visit, we might get something like, ``class Token must be declared abstract. It does not define void visit from interface Visitable.''

The next step is to modify the parser to put Token objects into the tree instead of Strings. Here is a small example:

verbatim String expr = "1 2 3 * +"; StringTokenizer st = new StringTokenizer (expr, " +-*/", true); String token = st.nextToken; Tree tree = new Tree (new Token (token), null, null)); verbatim

This code takes the first token in the string and wraps it in a Token object, then puts the Token into a tree node. If the Tree requires the cargo to be Visitable, it will convert the Token to be a Visitable object. When we remove the Visitable from the tree, we will have to cast it back into a Token.

As an exercise, write a version of printPreorder called visitPreorder that traverses the tree and invokes visit on each node in preorder.

Array implementation of trees
tree!array implementation implementation!Tree ADT!Tree

What does it mean to ``implement'' a tree? So far we have only seen one implementation of a tree, a linked data structure similar to a linked list. But there are other structures we would like to identify as trees. Anything that can perform the basic set of tree operations should be recognized as a tree.

So what are the tree operations? In other words, how do we define the Tree ADT?

description

[constructor:] Build an empty tree.

[isEmpty:] Is this tree the empty tree?

[getLeft:] Return the left child of this node.

[getRight:] Return the left child of this node.

[getParent:] Return the parent of this node.

[getCargo:] Return the cargo object from this node.

[setCargo:] Assign a cargo object to this node (and create the node, if necessary).

description

In the implementation we have seen, the empty tree is represented by the special value null. getLeft and getRight are performed by accessing the instance variables of the node, as are getCargo and setCargo. We have not implemented getParent yet (you might think about how to do it).

There is another implementation of trees that uses arrays and indices instead of objects and references. To see how it works, we will start by looking at a hybrid implementation that uses both arrays and objects.

This figure shows a tree like the ones we have been looking at, although it is laid out sideways, with the root at the left and the leaves on the right. At the bottom there is an array of references that refer to the objects in the trees. The cargo objects are represented as null references.

figure=figs/tree3.eps,width=5in

You might notice that array index 1 refers to the root node and array index 0 is empty. The reason for that will become clear soon.

So now we have a tree where each node has a unique index. Furthermore, the indices have been assigned to the nodes according to a deliberate pattern, in order to achieve the following results:

enumerate

The left child of the node with index has index.

The right child of the node with index has index.

The parent of the node with index has index  (rounded down).

enumerate

Using these formulas, we can implement getLeft, getRight and getParent just by doing arithmetic; we don't have to use the references at all!

Since we don't use the references, we can get rid of them, which means that what used to be a tree node is now just cargo and nothing else. That means we can implement the tree as an array of cargo objects; we don't need tree nodes at all.

Here's what one implementation looks like:

verbatim public class Tree Object[] array; int i;

public Tree array = new Object [128]; i = 1;

public Tree (Object[] array, int i)        this.array = array; this.i = i; verbatim

No surprises so far. The instance variables are an array of Objects and an integer that indicates where in the array the new node is found.

The first constructor initializes the array with an arbitrary initial size (we can always resize it later). The second constructor assumes that the array of objects already exists. All nodes that comprise a tree will share the same array and have different values of i.

We use i to access the cargo of a given node:

verbatim public Object getCargo if (i >= array.length) return null; return array[i];

public void setCargo (Object obj) if (i >= array.length) array = resize (array); array[i] = obj; verbatim

Both methods have to check the length of the array. If getCargo tries to access a nonexistent element of the array, it returns null to indicate an empty tree. If getCargo goes past the length of the array, it resizes the array to make room (see Section resize for a possible implementation of resize).

To check whether a node is an empty tree, we check whether the cargo is null.

verbatim public boolean empty return (getCargo == null); verbatim

The implementation of getLeft, getRight and getParent is just arithmetic:

verbatim public Tree getLeft return new Tree (array, 2*i);

public Tree getRight return new Tree (array, 2*i + 1);

public Tree parent return new Tree (array, i/2); verbatim

Finally we are ready to build a tree. In another class (the client), we would write

verbatim Tree tree = new Tree ; tree.setCargo ("cargo for root"); verbatim

The constructor builds an empty tree. Invoking setCargo puts the string "cargo for root" into the root node.

To add children to the root node:

verbatim tree.getLeft.setCargo ("cargo for left"); tree.getRight.setCargo ("cargo for right"); verbatim

In the tree class we could provide a method that prints the contents of the tree in preorder.

verbatim public void print if (isEmpty ) return; System.out.println (array[i]); getLeft.print; getRight.print; verbatim

We invoke this method from the client by passing the root as a parameter.

verbatim tree.print (root); verbatim

The output is

verbatim cargo for root cargo for left cargo for right verbatim

This implementation provides the basic operations that define a tree. As I pointed out, the linked implementation of a tree provides the same operations, but the syntax is different. As an exercise, modify the linked tree so that it implements the Tree ADT.

One problem with the array implementation is that the initial size of the array is arbitrary and it might have to be resized. This last problem can be solved by replacing the array with a Vector.

The Vector class
vector Vector class class!Vector

The Vector is a built-in Java class in the java.util package. It is an implementation of an array of Objects, with the added feature that it can resize itself automatically, so we don't have to.

The Vector class provides methods named get and set that are similar to the getCargo and setCargo methods we wrote for the Tree class. You should review the other Vector operations by consulting the online documentation.

Before using the Vector class, you should understand a few concepts. Every Vector has a capacity, which is the amount of space that has been allocated to store values, and a size, which is the number of values that are actually in the vector.

The following figure is a simple diagram of a Vector that contains three elements, but it has a capacity of seven.

figure=figs/vector.eps

In general, it is the responsibility of the client code to make sure that the vector has sufficient size before invoking set or get. If you try to access an element that does not exist (in this case the elements with indices 3 through 6), you will get an ArrayIndexOutOfBounds exception.

exception!ArrayIndexOutOfBounds ArrayIndexOutOfBounds

The Vector methods add and insert automatically increase the size of the Vector, but set does not. The resize method adds null elements to the end of the Vector to get to the given size.

Most of the time the client doesn't have to worry about capacity. Whenever the size of the Vector changes, the capacity is updated automatically. For performance reasons, some applications might want to take control of this function, which is why there are additional methods for increasing and decreasing capacity.

Because the client code has no access to the implementation of a vector, it is not clear how we should traverse one. Of course, one possibility is to use a loop variable as an index into the vector:

verbatim for (int i=0; i<v.size; i++) System.out.println (v.get(i)); verbatim

There's nothing wrong with that, but there is another way that serves to demonstrate the Iterator class. Vectors provide a method named iterator that returns an Iterator object that makes it possible to traverse the vector.

The Iterator class
iterator Iterator class class!Iterator abstract class

Iterator is an abstract class in the java.util package. It specifies three methods:

description

[hasNext:] Does this iteration have more elements?

[next:] Return the next element, or throw an exception if there is none.

[remove:] Remove from the collection the last element that was returned.

description

The following example uses an iterator to traverse and print the elements of a vector.

verbatim Iterator iterator = vector.iterator ; while (iterator.hasNext ) System.out.println (iterator.next ); verbatim

Once the Iterator is created, it is a separate object from the original Vector. Subsequent changes in the Vector are not reflected in the Iterator. In fact, if you modify the Vector after creating an Iterator, the Iterator becomes invalid. If you access the Iterator again, it will cause a ConcurrentModification exception.

exception!ConcurrentModification ConcurrentModification

In a previous section we used the Visitable abstract class to allow a client to traverse a data structure without knowing the details of its implementation. Iterators provide another way to do the same thing. In the first case, the provider performs the iteration and invokes client code to ``visit'' each element. In the second case the provider gives the client an object that it can use to select elements one at a time (albeit in an order controlled by the provider).

As an exercise, write a concrete class named PreIterator that implements the Iterator interface, and write a method named preorderIterator for the Tree class that returns a PreIterator that selects the elements of the Tree in preorder.

Glossary
binary tree root node leaf node parent node child node level prefix preorder postorder inorder class variable encapsulation

description

[binary tree:] A tree in which each node refers to 0, 1, or 2 dependent nodes.

[root:] The top-most node in a tree, to which no other nodes refer.

[leaf:] A bottom-most node in a tree, which refers to no other nodes.

[parent:] The node that refers to a given node.

[child:] One of the nodes referred to by a node.

[level:] The set of nodes equidistant from the root.

[prefix notation:] A way of writing a mathematical expression with each operator appearing before its operands.

[preorder:] A way to traverse a tree, visiting each node before its children.

[postorder:] A way to traverse a tree, visiting the children of each node before the node itself.

[inorder:] A way to traverse a tree, visiting the left subtree, then the root, then the right subtree.

[class variable:] A static variable declared outside of any method. It is accessible from any method.

[binary operator:] An operator that takes two operands.

[object encapsulation:] The design goal of keeping the implementations of two objects as separate as possible. Neither class should have to know the details of the implementation of the other.

[method encapsulation:] The design goal of keeping the interface of a method separate from the details of its implementation.

description

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: The Way of the Java/Trees


text:
The Way of the Java/The Slate Class

The Slate Class
verbatim import java.awt.*;

public class Example

// demonstrate simple use of the Slate class

public static void main (String[] args) int width = 500; int height = 500;

Slate slate = Slate.makeSlate (width, height); Graphics g = Slate.getGraphics (slate);

g.setColor (Color.blue); draw (g, 0, 0, width, height);

anim (slate, 0, 0, width, height);

// draw is taken from Section 4.14 of the book

public static void draw (Graphics g, int x, int y, int width, int height) if (height < 3) return;

g.drawOval (x, y, width, height);

draw (g, x, y+height/2, width/2, height/2); draw (g, x+width/2, y+height/2, width/2, height/2);

// anim demonstrates a simple animation

public static void anim (Slate slate, int x, int y, int width, int height) Graphics g = slate.image.getGraphics ; g.setColor (Color.red);

for (int i=-100; i<500; i+=8) g.drawOval (i, 100, 100, 100); slate.repaint ; try Thread.sleep(10); catch (InterruptedException e)

class Slate extends Frame

// image is a buffer: when Slate users draw things, they // draw on the buffer. When the Slate gets painted, we   // copy the image onto the screen. Image image;

public static Slate makeSlate (int width, int height) Slate s = new Slate ; s.setSize (width, height); s.setBackground (Color.white); s.setVisible (true); s.image = s.createImage (width, height); return s;

// when a Slate user asks for a Graphics object, we give // them one from the off-screen buffer.

public static Graphics getGraphics (Slate s)    return s.image.getGraphics ;

// normally update erases the screen and invokes paint, but // since we are overwriting the whole screen anyway, it is   // slightly faster to override update and avoid clearing the // screen

public void update (Graphics g)    paint (g);

// paint copies the off-screen buffer onto the screen

public void paint (Graphics g)    g.drawImage (image, 0, 0, null);

verbatim

title: The Way of the Java/The Slate Class


text:
The Way of the Java/Heap

The Heap
Heap ADT diagram!implementation

A heap is a special kind of tree that happens to be an efficient implementation of a priority queue. This figure shows the relationships among the data structures in this chapter.

figure=figs/heap_adt.eps

Ordinarily we try to maintain as much distance as possible between an ADT and its implementation, but in the case of the Heap, this barrier breaks down a little. The reason is that we are interested in the performance of the operations we implement. For each implementation there are some operations that are easy to implement and efficient, and others that are clumsy and slow.

It turns out that the array implementation of a tree works particularly well as an implementation of a Heap. The operations the array performs well are exactly the operations we need to implement a Heap.

To understand this relationship, we will proceed in a few steps. First, we need to develop ways of comparing the performance of various implementations. Next, we will look at the operations Heaps perform. Finally, we will compare the Heap implementation of a Priority Queue to the others (arrays and lists) and see why the Heap is considered particularly efficient.

Performance analysis
performance analysis run time algorithm analysis

When we compare algorithms, we would like to have a way to tell when one is faster than another, or takes less space, or uses less of some other resource. It is hard to answer those questions in detail, because the time and space used by an algorithm depend on the implementation of the algorithm, the particular problem being solved, and the hardware the program runs on.

The objective of this section is to develop a way of talking about performance that is independent of all of those things, and only depends on the algorithm itself. To start, we will focus on run time; later we will talk about other resources.

Our decisions are guided by a series of constraints:

enumerate

First, the performance of an algorithm depends on the hardware it runs on, so we usually don't talk about run time in absolute terms like seconds. Instead, we usually count the number of abstract operations the algorithm performs.

Second, performance often depends on the particular problem we are trying to solve -- some problems are easier than others. To compare algorithms, we usually focus on either the worst-case scenario or an average (or common) case.

Third, performance depends on the size of the problem (usually, but not always, the number of elements in a collection). We address this dependence explicitly by expressing run time as a function of problem size.

Finally, performance depends on details of the implementation like object allocation overhead and method invocation overhead. We usually ignore these details because they don't affect the rate at which the number of abstract operations increases with problem size.

enumerate

To make this process more concrete, consider two algorithms we have already seen for sorting an array of integers. The first is selection sort, which we saw in Section sorting. Here is the pseudocode we used there.

verbatim selectionsort (array) for (int i=0; i<array.length; i++) // find the lowest item at or to the right of i         // swap the ith item and the lowest item verbatim

To perform the operations specified in the pseudocode, we wrote helper methods named findLowest and swap. In pseudocode, findLowest looks like this

verbatim // find the index of the lowest item between // i and the end of the array

findLowest (array, i)        // lowest contains the index of the lowest item so far lowest = i;       for (int j=i+1; j<array.length; j++) // compare the jth item to the lowest item so far // if the jth item is lower, replace lowest with j       return lowest; verbatim

And swap looks like this:

verbatim swap (i, j)        // store a reference to the ith card in temp // make the ith element of the array refer to the jth card // make the jth element of the array refer to temp verbatim

To analyze the performance of this algorithm, the first step is to decide what operations to count. Obviously, the program does a lot of things: it increments i, compares it to the length of the deck, it searches for the largest element of the array, etc. It is not obvious what the right thing is to count.

sorting selection sort

It turns out that a good choice is the number of times we compare two items. Many other choices would yield the same result in the end, but this is easy to do and we will find that it allows us to compare most easily with other sort algorithms.

The next step is to define the ``problem size.'' In this case it is natural to choose the size of the array, which we'll call .

Finally, we would like to derive an expression that tells us how many abstract operations (specifically, comparisons) we have to do, as a function of.

helper method

We start by analyzing the helper methods. swap copies several references, but it doesn't perform any comparisons, so we ignore the time spent performing swaps. findLowest starts at i and traverses the array, comparing each item to lowest. The number of items we look at is, so the total number of comparisons is.

Next we consider how many times findLowest gets invoked and what the value of is each time. The last time it is invoked, is  so the number of comparisons is 1. The previous iteration performs 2 comparisons, and so on. During the first iteration, is  and the number of comparisons is.

So the total number of comparisons is. This sum is equal to. To describe this algorithm, we would typically ignore the lower order term and say that the total amount of work is proportional to. Since the leading order term is quadratic, we might also say that this algorithm is quadratic time.

quadratic time

Analysis of mergesort
mergesort analysis!mergesort sorting algorithm analysis

In Section mergesort I claimed that mergesort takes time that is proportional to, but I didn't explain how or why. Now I will.

Again, we start by looking at pseudocode for the algorithm. For mergesort, it's

verbatim mergeSort (array) // find the midpoint of the array // divide the array into two halves // sort the halves recursively // merge the two halves and return the result verbatim

At each level of the recursion, we split the array in half, make two recursive calls, and then merge the halves. Graphically, the process looks like this:

figure=figs/mergetree.eps,width=5in

Each line in the diagram is a level of the recursion. At the top, a single array divides into two halves. At the bottom, arrays (with one element each) are merged into arrays (with 2 elements each).

recursion

The first two columns of the table show the number of arrays at each level and the number of items in each array. The third column shows the number of merges that take place at each level of recursion. The next column is the one that takes the most thought: it shows the number of comparisons each merge performs.

pseudocode

If you look at the pseudocode (or your implementation) of merge, you should convince yourself that in the worst case it takes comparisons, where  is the total number items being merged.

The next step is to multiply the number of merges at each level by the amount of work (comparisons) per merge. The result is the total work at each level. At this point we take advantage of a small trick. We know that in the end we are only interested in the leading-order term in the result, so we can go ahead and ignore the term in the comparisons per merge. If we do that, then the total work at each level is simply.

Next we need to know the number of levels as a function of. Well, we start with an array of items and divide it in half until it gets to 1. That's the same as starting at 1 and multiplying by 2 until we get to. In other words, we want to know how many times we have to multiply 2 by itself before we get to. The answer is that the number of levels,, is the logarithm, base 2, of.

Finally, we multiply the amount of work per level,, by the number of levels, to get, as promised. There isn't a good name for this functional form; most of the time people just say, ``en log en.''

It might not be obvious at first that is better than , but for large values of, it is. As an exercise, write a program that prints and for a range of values of.

Overhead
overhead

Performance analysis takes a lot of handwaving. First we ignored most of the operations the program performs and counted only comparisons. Then we decided to consider only worst case performance. During the analysis we took the liberty of rounding a few things off, and when we finished, we casually discarded the lower-order terms.

When we interpret the results of this analysis, we have to keep all this hand-waving in mind. Because mergesort is , we consider it a better algorithm than selection sort, but that doesn't mean that mergesort is always faster. It just means that eventually, if we sort bigger and bigger arrays, mergesort will win.

How long that takes depends on the details of the implementation, including the additional work, besides the comparisons we counted, that each algorithm performs. This extra work is sometimes called overhead. It doesn't affect the performance analysis, but it does affect the run time of the algorithm.

For example, our implementation of mergesort actually allocates subarrays before making the recursive calls and then lets them get garbage collected after they are merged. Looking again at the diagram of mergesort, we can see that the total amount of space that gets allocated is proportional to, and the total number of objects that get allocated is about. All that allocating takes time.

Even so, it is most often true that a bad implementation of a good algorithm is better than a good implementation of a bad algorithm. The reason is that for large values of the good algorithm is better and for small values of  it doesn't matter because both algorithms are good enough.

As an exercise, write a program that prints values of and for a range of values of. For what value of are they equal?

Priority Queue implementations
implementation!Priority Queue analysis!Priority Queue priority queue!sorted list implementation

In Chapter queue we looked at an implementation of a Priority Queue based on an array. The items in the array are unsorted, so it is easy to add a new item (at the end), but harder to remove an item, because we have to search for the item with the highest priority.

An alternative is an implementation based on a sorted list. In this case when we insert a new item we traverse the list and put the new item in the right spot. This implementation takes advantage of a property of lists, which is that it is easy to insert a new node into the middle. Similarly, removing the item with the highest priority is easy, provided that we keep it at the beginning of the list.

Performance analysis of these operations is straightforward. Adding an item to the end of an array or removing a node from the beginning of a list takes the same amount of time regardless of the number of items. So both operations are constant time.

constant time

Any time we traverse an array or list, performing a constant-time operation on each element, the run time is proportional to the number of items. Thus, removing something from the array and adding something to the list are both linear time.

linear time

So how long does it take to insert and then remove items from a Priority Queue? For the array implementation, insertions takes time proportional to, but the removals take longer. The first removal has to traverse all items; the second has to traverse, and so on, until the last removal, which only has to look at 1 item. Thus, the total time is, which is (still). So the total for the insertions and the removals is the sum of a linear function and a quadratic function. The leading term of the result is quadratic.

The analysis of the list implementation is similar. The first insertion doesn't require any traversal, but after that we have to traverse at least part of the list each time we insert a new item. In general we don't know how much of the list we will have to traverse, since it depends on the data and what order they are inserted, but we can assume that on average we have to traverse half of the list. Unfortunately, even traversing half of the list is still a linear operation.

So, once again, to insert and remove items takes time proportional to. Thus, based on this analysis we cannot say which implementation is better; both the array and the list yield quadratic run times.

If we implement a Priority Queue using a heap, we can perform both insertions and removals in time proportional to. Thus the total time for items is , which is better than. That's why, at the beginning of the chapter, I said that a heap is a particularly efficient implementation of a Priority Queue.

Definition of a Heap
Heap!definition tree complete tree tree!complete heap property

A heap is a special kind of tree. It has two properties that are not generally true for other trees:

description

[completeness:] The tree is complete, which means that nodes are added from top to bottom, left to right, without leaving any spaces.

[heapness:] The item in the tree with the highest priority is at the top of the tree, and the same is true for every subtree.

description

Both of these properties call for a little explaining. This figure shows a number of trees that are considered complete or not complete:

figure=figs/tree4.eps,width=4in

An empty tree is also considered complete. We can define completeness more rigorously by comparing the height of the subtrees. Recall that the height of a tree is the number of levels.

height

Starting at the root, if the tree is complete, then the height of the left subtree and the height of the right subtree should be equal, or the left subtree may be taller by one. In any other case, the tree cannot be complete.

Furthermore, if the tree is complete, then the height relationship between the subtrees has to be true for every node in the tree.

It is natural to write these rules as a recursive method:

verbatim public static boolean isComplete (Tree tree) // the null tree is complete if (tree == null) return true;

int leftHeight = height (tree.left); int rightHeight = height (tree.right); int diff = leftHeight - rightHeight;

// check the root node if (diff 1) return false;

// check the children if (!isComplete (tree.left)) return false; return isComplete (tree.right); verbatim

For this example I used the linked implementation of a tree. As an exercise, write the same method for the array implementation. Also as an exercise, write the height method. The height of a null tree is 0 and the height of a leaf node is 1.

recursive definition

The heap property is similarly recursive. In order for a tree to be a heap, the largest value in the tree has to be at the root, and the same has to be true for each subtree. As another exercise, write a method that checks whether a tree has the heap property.

Heap remove
reheapify

It might seem odd that we are going to remove things from the heap before we insert any, but I think removal is easier to explain.

At first glance, we might think that removing an item from the heap is a constant time operation, since the item with the highest priority is always at the root. The problem is that once we remove the root node, we are left with something that is no longer a heap. Before we can return the result, we have to restore the heap property. We call this operation reheapify.

The situation is shown in the following figure:

figure=figs/tree5.eps,height=2in

The root node has priority r and two subtrees, A and B. The value at the root of Subtree A is a and the value at the root of Subtree B is b.

We assume that before we remove r from the tree, the tree is a heap. That implies that r is the largest value in the heap and that a and b are the largest values in their respective subtrees.

Once we remove r, we have to make the resulting tree a heap again. In other words we need to make sure it has the properties of completeness and heapness.

The best way to ensure completeness is to remove the bottom-most, right-most node, which we'll call c and put its value at the root. In a general tree implementation, we would have to traverse the tree to find this node, but in the array implementation, we can find it in constant time because it is always the last (non-null) element of the array.

Of course, the chances are that the last value is not the highest, so putting it at the root breaks the heapness property. Fortunately it is easy to restore. We know that the largest value in the heap is either a or b. Therefore we can select whichever is larger and swap it with the value at the root.

Arbitrarily, let's say that b is larger. Since we know it is the highest value left in the heap, we can put it at the root and put c at the top of Subtree B. Now the situation looks like this:

figure=figs/tree6.eps,height=2in

Again, c is the value we copied from the last entry in the array and b is the highest value left in the heap. Since we haven't changed Subtree A at all, we know that it is still a heap. The only problem is that we don't know if Subtree B is a heap, since we just stuck a (probably low) value at its root.

recursion

Wouldn't it be nice if we had a method that could reheapify Subtree B? Wait... we do!

Heap insert
Inserting a new item in a heap is a similar operation, except that instead of trickling a value down from the top, we trickle it up from the bottom.

Again, to guarantee completeness, we add the new element at the bottom-most, rightmost position in the tree, which is the next available space in the array.

Then to restore the heap property, we compare the new value with its neighbors. The situation looks like this:

figure=figs/tree7.eps,height=2in

The new value is c. We can restore the heap property of this subtree by comparing c to a. If c is smaller, then the heap property is satisfied. If c is larger, then we swap c and a. The swap satisfies the heap property because we know that c must also be bigger than b, because c > a and a > b.

Now that the subtree is reheapified, we can work our way up the tree until we reach the root.

Performance of heaps
Heap!analysis analysis!Heap

For both insert and remove, we perform a constant time operation to do the actual insertion and removal, but then we have to reheapify the tree. In one case we start at the root and work our way down, comparing items and then recursively reheapifying one of the subtrees. In the other case we start at a leaf and work our way up, again comparing elements at each level of the tree.

As usual, there are several operations we might want to count, like comparisons and swaps. Either choice would work; the real issue is the number of levels of the tree we examine and how much work we do at each level. In both cases we keep examining levels of the tree until we restore the heap property, which means we might only visit one, or in the worst case we might have to visit them all. Let's consider the worst case.

At each level, we perform only constant time operations like comparisons and swaps. So the total amount of work is proportional to the number of levels in the tree, a.k.a. the height.

So we might say that these operations are linear with respect to the height of the tree, but the ``problem size'' we are interested in is not height, it's the number of items in the heap.

As a function of, the height of the tree is. This is not true for all trees, but it is true for complete trees. To see why, think of the number of nodes on each level of the tree. The first level contains 1, the second contains 2, the third contains 4, and so on. The th level contains nodes, and the total number in all levels up to is .  In other words,, which means that .

logarithmic time

Thus, both insertion and removal take logarithmic time. To insert and remove items takes time proportional to.

Heapsort
heapsort sorting analysis!heapsort

The result of the previous section suggests yet another algorithm for sorting. Given items, we insert them into a Heap and then remove them. Because of the Heap semantics, they come out in order. We have already shown that this algorithm, which is called heapsort, takes time proportional to , which is better than selection sort and the same as mergesort.

As the value of gets large, we expect heapsort to be faster than selection sort, but performance analysis gives us no way to know whether it will be faster than mergesort. We would say that the two algorithms have the same order of growth because they grow with the same functional form. Another way to say the same thing is that they belong to the same complexity class.

big-O notation complexity class order of growth constant time linear time quadratic time logarithmic time

Complexity classes are sometimes written in ``big-O notation''. For example,, pronounced ``oh of en squared'' is the set of all functions that grow no faster than for large values of. To say that an algorithm is is the same as saying that it is quadratic. The other complexity classes we have seen, in decreasing order of performance, are:

0.2in tabularll & constant time & logarithmic & linear & ``en log en'' & quadratic & exponential tabular 0.2in

So far none of the algorithms we have looked at are exponential. For large values of, these algorithms quickly become impractical. Nevertheless, the phrase ``exponential growth'' appears frequently in even non-technical language. It is frequently misused so I wanted to include its technical meaning.

People often use ``exponential'' to describe any curve that is increasing and accelerating (that is, one that has positive slope and curvature). Of course, there are many other curves that fit this description, including quadratic functions (and higher-order polynomials) and even functions as undramatic as. Most of these curves do not have the (often detrimental) explosive behavior of exponentials.

As an exercise, compare the behavior of and as the value of increases.

Glossary
selection sort mergesort heapsort complexity class order of growth overhead

description

[selection sort:] The simple sorting algorithm in Section sorting.

[mergesort:] A better sorting algorithm from Section mergesort.

[heapsort:] Yet another sorting algorithm.

[complexity class:] A set of algorithms whose performance (usually run time) has the same order of growth.

[order of growth:] A set of functions with the same leading-order term, and therefore the same qualitative behavior for large values of.

[overhead:] Additional time or resources consumed by a programming performing operations other than the abstract operations considered in performance analysis.

title: The Way of the Java/Heap