_Treaps in Java_ 
by Stefan Nilsson

Listing One
/* An interface for ordered objects. A class that is to be used
 * as a key in a treap must implement this interface. */
public interface Ordered
{
   /* Compares two ordered objects. Returns the value 0 if this object equals 
    * the argument; a value less that 0 if this object is less than argument; 
    * and a value larger than 0 if this object is greater than the argument. */
   int compareTo(Ordered anotherOrderedObject);
}


Listing Two
import order.*;
import java.util.Enumeration;

class Year implements Ordered
{
   int year;   
   Year(int y) { year = y; }
   public int compareTo(Ordered y) {
      if (year > ((Year) y).year)
         return 1;
      else if (year < ((Year) y).year)
         return -1;
      else
         return 0;
   }
   public String toString() {
      return Integer.toString(year);
   }
}
class TreapDemo
{
   public static void main(String[] args) {
      Treap treap = new Treap();
      treap.put(new Year(1935), "Elvis Presley");
      treap.put(new Year(1926), "Chuck Berry");
      treap.put(new Year(1941), "Bob Dylan");
      treap.put(new Year(1936), "Roy Orbison");
      treap.put(new Year(1915), "Muddy Waters");
      Enumeration k = treap.keys();
      Enumeration e = treap.elements();
      while (k.hasMoreElements()) {
         System.out.print(k.nextElement() + ": ");
         System.out.println(e.nextElement());
      }
   }
}


