Project Euler Problem 448 and the GMP Library: Part 2

Below is prototypical program that uses the gmp.h interface to compute the product of two very large numbers. According to the documentation, you have to both declare and initialize a variable before you can use it.

#include < stdio.h >
#include <stdlib.h>
#include <gmp.h>
 
int main(void)
{
/*gmp variable declarations*/
 mpz_t x;
 mpz_t y;
 mpz_t result;
 
/*variable initializations*/
 mpz_init(x);/*make room for x*/
 mpz_init(y);
 mpz_init(result);
 /* these functions are the equivalent of variable assignments; note
    the extra parameter 10 stands for radix, or base*/
 mpz_set_str(x, "7612058254738945", 10);/* this says x holds a big base 10 integer*/
 mpz_set_str(y, "9263591128439081", 10);
 
/*this function is where the actual computation takes place:
  it stores x*y in result*/
 mpz_mul(result, x, y);
/* this function is the gmp extension of the standard printf function
the format specifier is Zd which we can take to mean big int*/
 gmp_printf("\n    %Zd\n*\n    %Zd\n--------------------\n%Zd\n\n", x, y, result);
 
 /* free used memory */
 mpz_clear(x);
 mpz_clear(y);
 mpz_clear(result);
 return EXIT_SUCCESS;
}

Notice how complicated this was. This program really doesn't do anything at all interesting. All you can take from this is that interacting with the gmp library requires a lot of boiler plate. If that was uninteresting let's do something a little interesting: the factorial function.

#include < stdio.h >
#include <stdlib.h>
#include <gmp.h>
#include <assert.h>
 
void fact(int n){
  int i;
  mpz_t fact;
 /*this is a convenient function that helps avoid some of that
    boiler plate: it both declares and initializes in one step*/
  mpz_init_set_ui(fact,1); /* fact = 1 */
  for (i=1; i <= n ; ++i){
    mpz_mul_ui(fact,fact,i); /* fact = fact * i */
  }
  
  gmp_printf ("%d!= %Zd ",n,fact);
  mpz_clear(fact);
 
}
 
int main(int argc, char * argv[]){
  int n;
 
 
  if (argc <= 1){
    printf ("Usage: %s <number> \n", argv[0]);
    return 2;
  }
 
  n = atoi(argv[1]);/*convert commandline arg to int*/
  assert( n >= 0);/*check operation success*/
  fact(n);
 
 
  return 0;
}

Next post, I will test the lcm functions in the gmp library and finally get that solution.

Graphs in Java Version 1

import java.util.*;

public abstract class AbstractGraph implements Graph {
  protected List vertices = new ArrayList(); // Store vertices
  protected List> neighbors 
    = new ArrayList>(); // Adjacency lists

  /** Construct an empty graph */
  protected AbstractGraph() {
  }
  
  /** Construct a graph from edges and vertices stored in arrays */
  protected AbstractGraph(int[][] edges, V[] vertices) {
    for (int i = 0; i < vertices.length; i++)
      this.vertices.add(vertices[i]);
    
    createAdjacencyLists(edges, vertices.length);
  }

  /** Construct a graph from edges and vertices stored in List */
  protected AbstractGraph(List edges, List vertices) {
	for (int i = 0; i < vertices.size(); i++)
	  this.vertices.add(vertices.get(i));
	    
	createAdjacencyLists(edges, vertices.size());
  }

  /** Construct a graph for integer vertices 0, 1, 2 and edge list */
  protected AbstractGraph(List edges, int numberOfVertices) {
    for (int i = 0; i < numberOfVertices; i++) {
      vertices.add((V)(new Integer(i))); // vertices is {0, 1, ...}
    }
    createAdjacencyLists(edges, numberOfVertices);
  }

  /** Construct a graph from integer vertices 0, 1, and edge array */
  protected AbstractGraph(int[][] edges, int numberOfVertices) {
    for (int i = 0; i < numberOfVertices; i++) {
      vertices.add((V)(new Integer(i))); // vertices is {0, 1, ...}
    }
    createAdjacencyLists(edges, numberOfVertices);
  }

  /** Create adjacency lists for each vertex */
  private void createAdjacencyLists(
      int[][] edges, int numberOfVertices) {
    // Create a linked list
    for (int i = 0; i < numberOfVertices; i++) {
      neighbors.add(new ArrayList());
    }

    for (int i = 0; i < edges.length; i++) {
      int u = edges[i][0];
      int v = edges[i][1];
      neighbors.get(u).add(v);
    }
  }

  /** Create adjacency lists for each vertex */
  private void createAdjacencyLists(
      List edges, int numberOfVertices) {
    // Create a linked list for each vertex
    for (int i = 0; i < numberOfVertices; i++) {
      neighbors.add(new ArrayList());
    }

    for (Edge edge: edges) {
      neighbors.get(edge.u).add(edge.v);
    }
  }

  /** Return the number of vertices in the graph */
  public int getSize() {
    return vertices.size();
  }

  /** Return the vertices in the graph */
  public List getVertices() {
    return vertices;
  }

  /** Return the object for the specified vertex */
  public V getVertex(int index) {
    return vertices.get(index);
  }

  /** Return the index for the specified vertex object */
  public int getIndex(V v) {
    return vertices.indexOf(v);
  }

  /** Return the neighbors of vertex with the specified index */
  public List getNeighbors(int index) {
    return neighbors.get(index);
  }

  /** Return the degree for a specified vertex */
  public int getDegree(int v) {
    return neighbors.get(v).size();
  }

  /** Print the edges */
  public void printEdges() {
    for (int u = 0; u < neighbors.size(); u++) {
      System.out.print(getVertex(u) + " (" + u + "): ");
      for (int j = 0; j < neighbors.get(u).size(); j++) {
        System.out.print("(" + u + ", " +
          neighbors.get(u).get(j) + ") ");
      }
      System.out.println();
    }
  }

  /** Clear graph */
  public void clear() {
	vertices.clear();
	neighbors.clear();
  }
  
  /** Add a vertex to the graph */  
  public void addVertex(V vertex) {
    vertices.add(vertex);
    neighbors.add(new ArrayList());
  }

  /** Add an edge to the graph */  
  public void addEdge(int u, int v) {
    neighbors.get(u).add(v);
    neighbors.get(v).add(u);
  }
  
  /** Edge inner class inside the AbstractGraph class */
  public static class Edge {
    public int u; // Starting vertex of the edge
    public int v; // Ending vertex of the edge

    /** Construct an edge for (u, v) */
    public Edge(int u, int v) {
      this.u = u;
      this.v = v;
    }
  }
  
  /** Obtain a DFS tree starting from vertex v */
  public Tree dfs(int v) {
    List searchOrders = new ArrayList();
    int[] parent = new int[vertices.size()];
    for (int i = 0; i < parent.length; i++)
      parent[i] = -1; // Initialize parent[i] to -1

    // Mark visited vertices
    boolean[] isVisited = new boolean[vertices.size()];

    // Recursively search
    dfs(v, parent, searchOrders, isVisited);

    // Return a search tree
    return new Tree(v, parent, searchOrders);
  }

  /** Recursive method for DFS search */
  private void dfs(int v, int[] parent, List searchOrders,
      boolean[] isVisited) {
    // Store the visited vertex
    searchOrders.add(v);
    isVisited[v] = true; // Vertex v visited

    for (int i : neighbors.get(v)) {
      if (!isVisited[i]) {
        parent[i] = v; // The parent of vertex i is v
        dfs(i, parent, searchOrders, isVisited); // Recursive search
      }
    }
  }

  /** Starting bfs search from vertex v */
  /** To be discussed in Section 27.7 */
  public Tree bfs(int v) {
    List searchOrders = new ArrayList();
    int[] parent = new int[vertices.size()];
    for (int i = 0; i < parent.length; i++)
      parent[i] = -1; // Initialize parent[i] to -1

    java.util.LinkedList queue =
      new java.util.LinkedList(); // list used as a queue
    boolean[] isVisited = new boolean[vertices.size()];
    queue.offer(v); // Enqueue v
    isVisited[v] = true; // Mark it visited

    while (!queue.isEmpty()) {
      int u = queue.poll(); // Dequeue to u
      searchOrders.add(u); // u searched
      for (int w : neighbors.get(u)) {
        if (!isVisited[w]) {
          queue.offer(w); // Enqueue w
          parent[w] = u; // The parent of w is u
          isVisited[w] = true; // Mark it visited
        }
      }
    }

    return new Tree(v, parent, searchOrders);
  }

  /** Tree inner class inside the AbstractGraph class */
  /** To be discussed in Section 27.5 */
  public class Tree {
    private int root; // The root of the tree
    private int[] parent; // Store the parent of each vertex
    private List searchOrders; // Store the search order

    /** Construct a tree with root, parent, and searchOrder */
    public Tree(int root, int[] parent, List searchOrders) {
      this.root = root;
      this.parent = parent;
      this.searchOrders = searchOrders;
    }

    /** Return the root of the tree */
    public int getRoot() {
      return root;
    }

    /** Return the parent of vertex v */
    public int getParent(int v) {
      return parent[v];
    }

    /** Return an array representing search order */
    public List getSearchOrders() {
      return searchOrders;
    }

    /** Return number of vertices found */
    public int getNumberOfVerticesFound() {
      return searchOrders.size();
    }
    
    /** Return the path of vertices from a vertex index to the root */
    public List getPath(int index) {
      ArrayList path = new ArrayList();

      do {
        path.add(vertices.get(index));
        index = parent[index];
      }
      while (index != -1);

      return path;
    }

    /** Print a path from the root to vertex v */
    public void printPath(int index) {
      List path = getPath(index);
      System.out.print("A path from " + vertices.get(root) + " to " +
        vertices.get(index) + ": ");
      for (int i = path.size() - 1; i >= 0; i--)
        System.out.print(path.get(i) + " ");
    }

    /** Print the whole tree */
    public void printTree() {
      System.out.println("Root is: " + vertices.get(root));
      System.out.print("Edges: ");
      for (int i = 0; i < parent.length; i++) {
        if (parent[i] != -1) {
          // Display an edge
          System.out.print("(" + vertices.get(parent[i]) + ", " +
            vertices.get(i) + ") ");
        }
      }
      System.out.println();
    }
  }
  
  /** Return a Hamiltonian path from the specified vertex object
   * Return null if the graph does not contain a Hamiltonian path */
  public List getHamiltonianPath(V vertex) {
    return getHamiltonianPath(getIndex(vertex));
  }

  /** Return a Hamiltonian path from the specified vertex label
   * Return null if the graph does not contain a Hamiltonian path */
  public List getHamiltonianPath(int v) {
    // A path starts from v. (i, next[i]) represents an edge in 
    // the path. isVisited[i] tracks whether i is currently in the 
    // path.
    int[] next = new int[getSize()];       
    for (int i = 0; i < next.length; i++)
      next[i] = -1; // Indicate no subpath from i is found yet
    
    boolean[] isVisited = new boolean[getSize()]; 
    
    // The vertices in the Hamiltonian path are stored in result
    List result = null;

    // To speed up search, reorder the adjacency list for each 
    // vertex so that the vertices in the list are in increasing 
    // order of their degrees
    for (int i = 0; i < getSize(); i++)
      reorderNeigborsBasedOnDegree(neighbors.get(i));
    
    if (getHamiltonianPath(v, next, isVisited)) {
      result = new ArrayList(); // Create a list for path        
      int vertex = v; // Starting from v
      while (vertex != -1) {
        result.add(vertex); // Add vertex to the result list
        vertex = next[vertex]; // Get the next vertex in the path
      }
    }
    
    return result; // return null if no Hamiltonian path is found
  }

  /** Reorder the adjacency list in increasing order of degrees */
  private void reorderNeigborsBasedOnDegree(List list) {
    for (int i = list.size() - 1; i >= 1; i--) {
      // Find the maximum in the list[0..i]
      int currentMaxDegree = getDegree(list.get(0));
      int currentMaxIndex = 0;

      for (int j = 1; j <= i; j++) {
        if (currentMaxDegree < getDegree(list.get(j))) { 
          currentMaxDegree = getDegree(list.get(j));
          currentMaxIndex = j;
        }
      }

      // Swap list[i] with list[currentMaxIndex] if necessary;
      if (currentMaxIndex != i) {
        int temp = list.get(currentMaxIndex);
        list.set(currentMaxIndex, list.get(i));
        list.set(i, temp);
      }
    }
  }
  
  /** Return true if all elements in array isVisited are true */
  private boolean allVisited(boolean[] isVisited) {
    boolean result = true;
    
    for (int i = 0; i < getSize(); i++) 
      result = result && isVisited[i];
    
    return result;
  }
  
  /** Search for a Hamiltonian path from v */
  private boolean getHamiltonianPath(int v, int[] next,
      boolean[] isVisited) {
    isVisited[v] = true; // Mark vertex v visited

    if (allVisited(isVisited)) 
      return true; // The path now includes all vertices, thus found
      
    for (int i = 0; i < neighbors.get(v).size(); i++) {
      int u = neighbors.get(v).get(i);
      if (!isVisited[u] && 
          getHamiltonianPath(u, next, isVisited)) {
        next[v] = u; // Edge (v, u) is in the path
        return true; 
      }
    }

    isVisited[v] = false; // Backtrack, v is marked unvisited now
    return false; // No Hamiltonian path exists from vertex v
  }
}

public interface Graph {
  /** Return the number of vertices in the graph */
  public int getSize();

  /** Return the vertices in the graph */
  public java.util.List getVertices();

  /** Return the object for the specified vertex index */
  public V getVertex(int index);

  /** Return the index for the specified vertex object */
  public int getIndex(V v);

  /** Return the neighbors of vertex with the specified index */
  public java.util.List getNeighbors(int index);

  /** Return the degree for a specified vertex */
  public int getDegree(int v);

  /** Print the edges */
  public void printEdges();

  /** Clear graph */
  public void clear();

  /** Add a vertex to the graph */  
  public void addVertex(V vertex);

  /** Add an edge to the graph */  
  public void addEdge(int u, int v);

  /** Obtain a depth-first search tree */
  public AbstractGraph.Tree dfs(int v);

  /** Obtain a breadth-first search tree */
  public AbstractGraph.Tree bfs(int v);
}

public class TestGraph {
  public static void main(String[] args) {
    String[] vertices = {"Seattle", "San Francisco", "Los Angeles",
      "Denver", "Kansas City", "Chicago", "Boston", "New York",
      "Atlanta", "Miami", "Dallas", "Houston"};

    // Edge array for graph
    int[][] edges = {
      {0, 1}, {0, 3}, {0, 5},
      {1, 0}, {1, 2}, {1, 3},
      {2, 1}, {2, 3}, {2, 4}, {2, 10},
      {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
      {4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
      {5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
      {6, 5}, {6, 7},
      {7, 4}, {7, 5}, {7, 6}, {7, 8},
      {8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
      {9, 8}, {9, 11},
      {10, 2}, {10, 4}, {10, 8}, {10, 11},
      {11, 8}, {11, 9}, {11, 10}
    };

    Graph graph1 = 
      new UnweightedGraph(edges, vertices);
    System.out.println("The number of vertices in graph1: " 
      + graph1.getSize());
    System.out.println("The vertex with index 1 is " 
      + graph1.getVertex(1));
    System.out.println("The index for Miami is " + 
      graph1.getIndex("Miami"));
    System.out.println("The edges for graph1:");
    graph1.printEdges();

    // List of Edge objects for graph in Figure 27.3(a)
    String[] names = {"Peter", "Jane", "Mark", "Cindy", "Wendy"};
    java.util.ArrayList edgeList
      = new java.util.ArrayList();
    edgeList.add(new AbstractGraph.Edge(0, 2));
    edgeList.add(new AbstractGraph.Edge(1, 2));
    edgeList.add(new AbstractGraph.Edge(2, 4));
    edgeList.add(new AbstractGraph.Edge(3, 4));
    // Create a graph with 5 vertices
    Graph graph2 = new UnweightedGraph
      (edgeList, java.util.Arrays.asList(names));
    System.out.println("\nThe number of vertices in graph2: " 
      + graph2.getSize());
    System.out.println("The edges for graph2:");
    graph2.printEdges();
  }
}

Comments: This design can be criticized in a some ways. By design I mean choosing to make a abstract class, interface, and a concrete class. So the goal of this is to make a small usable graphs/graph algorithms api in java for display purposes. If we really want to implement provably fast algorithms, we need to reify the design from the perspective of minimizing both time and space. With that end in mind, in the near future, I will present

a nonrecursive version of DFS

a method to read in a graph from a file containing data in the following format: v1-v2,v3,v4,v4;

solutions to the Euler path problem, Hamiltonian path problem, topological sort

Project Euler Problem 448 and an Intro to the GMP library:PART 1

This post contains my solution to project euler problem 448, . The GMP library is for arbitrary precision arithmetic calculations. Now why would I have to pull that out to solve this problem. Well, problem 448 deals with large numbers and I also want to get acquainted with that library. So here's an algorithm in pseudocode that will eventually become a solution to that problem.

int gcd(int a, int b){
    if b==0 return a;
    else return gcd(b, a mod b);
}

int lcm(int a, int b){
    return gcd(a,b)/(a*b);
}

int Avglcm(int n){
    int sum;
    for i=1 to n
        sum += lcm(i,n)
    return (sum/n);
}

SumAvg(int n){
    int total;
    for j=1 to n
        total +=Avglcm(j);
    return total;   
}

Normally, these subroutines would be sufficient to give to a main function and then just calculate the desired values. However, the values we are dealing with are pretty big and I want the optimal performance for this algorithm. So I need the Gnu MP library. Here's a link to the online manual: https://gmplib.org/manual/index.html#Top We are interested in basic number-theoretic functions: lcm and gcd. But before we go that far we need to know how to interact with the library. There's no getting around the fact that we need to read the GMP Basics. So here is bullet-pointed version:

• GMP functions generally have output arguments before input arguments.  This means a function like mpz_mul(x,y,z) assigns y*z to x
• For variables, it gets even more weird: not only do you have declare a variable of a gmp type, say "mpz_t n;" you also have to initialize n with something like "mpz_init(n);" now its ready to use.
• Strangest of all is that all of these functions have a signature like so: void mpz_func(result, op1,op2), which means they all return void. As someone from javaland, these weirds me out. I m guessing there is a convention here that if there is no return statement, the last calculation is returned by default.
• We are also interested in basic integer I/O. The GMP library has *printf functions for every gmp type. GMP adds the format specifiers: ‘Z’, ‘Q’ and ‘F’ for mpz_t, mpq_t and mpf_t respectively, ‘M’ for mp_limb_t, and ‘N’ for an mp_limb_t array. ‘Z’, ‘Q’, ‘M’ and ‘N’ behave like integers. ‘Q’ will print a ‘/’ and a denominator, if needed. ‘F’ behaves like a float. The section on formatted I/O even has nice examples, such as:"mpz_t z; gmp_printf ("%s is an mpz %Zd\n", "here", z);" This is probably something we'll have use for.

Graphs And Graph Algorithms: The Holy Grail of Computer Science

#define len 6//number of nodes

struct node 
{
    struct node *next;
    int vertex;
};
//function to allocate space for one node
struct node *nalloc(void)
{
    return (struct node *)malloc(sizeof(struct node));    
}
//function for making a node from int
struct node *makenode(int vertex)
{
    struct node *temp=nalloc();
    temp->vertex=vertex;
    temp->next=NULL;
    return temp;
}
//function for connecting two nodes.
struct node *addnode(struct node *p, int vertex)
{
       if(p == NULL) //if first node in list
       {   
           p=nalloc();//make space for p
           p->next=NULL;
           p->vertex=vertex;
       }else{//this is not first node
           p->next=nalloc();//make space
           p->next->vertex=vertex;
       }
       return p;
}
int main()
{    
    struct node{
          struct node* next;
          int vertex;
};
    struct node array[len]={{NULL,1},
                            {NULL,2},
                            {NULL,3},
                            {NULL,4},
                            {NULL,5},
                            {NULL,6},
    };//end arraylist
  
    //print each head of list
    int j;
    for(j=0; jnext->vertex);
     
return 0;
}

I call graphs and graph algorithms the holy grail of CS because they have suchwide, disparate applications throughout the sciences. This post represents myfirst clumsy grope at the problems posed by considering the processing of graphs.

Quicksort: Version 1

// Comment
public class QuickSort {
  public static void quickSort(int[] list) {
    quickSort(list, 0, list.length - 1);
  }

  private static void quickSort(int[] list, int first, int last) {
    if (last > first) {
      int pivotIndex = partition(list, first, last);
      quickSort(list, first, pivotIndex - 1);
      quickSort(list, pivotIndex + 1, last);
    }
  }

  /** Partition the array list[first..last] */
  private static int partition(int[] list, int first, int last) {
    int pivot = list[first]; // Choose the first element as the pivot
    int low = first + 1; // Index for forward search
    int high = last; // Index for backward search

    while (high > low) {
      // Search forward from left
      while (low <= high && list[low] <= pivot)
        low++;

      // Search backward from right
      while (low <= high && list[high] > pivot)
        high--;

      // Swap two elements in the list
      if (high > low) {
        int temp = list[high];
        list[high] = list[low];
        list[low] = temp;
      }
    }

    while (high > first && list[high] >= pivot)
      high--;

    // Swap pivot with list[high]
    if (pivot > list[high]) {
      list[first] = list[high];
      list[high] = pivot;
      return high;
    }
    else {
      return first;
    }
  }

  /** A test method */
  public static void main(String[] args) {
    int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
    quickSort(list);
    for (int i = 0; i < list.length; i++)
      System.out.print(list[i] + " ");
  }
}

Commentary:

 This is my first version of the well-known QuickSort algorithm. I actually don't like it but it s a standard implementation patterned after the algorithm presented in Cormen's Intro to Algorithms. In the future, I will make this non-recursive, randomized and generic and type-safe.

Randomly Built Binary Search Tree in C

#include 
#include 
#include 

struct btreenode 
{
    int key;
    struct btreenode *left;
    struct btreenode *right;
    struct btreenode *parent;
};

struct btreenode* btralloc(void)//function to allocate space for new node
{
    return (struct btreenode *)malloc(sizeof(struct btreenode)); 
}   //type coercion used because malloc returns void*

struct btreenode *addnode(struct btreenode *p, int num)
{
       if (p == NULL)
       {  
           p=btralloc();//allocate space for new node
           p->key=num;
           p->left=p->right=p->parent=NULL;
       }
       else if (p->key < num) //key < num means put num in right child 
           {
            //make current node parent of next node
            p->right=addnode(p->right, num);
            p->right->parent=p;
           }
       else {
           //make current node parent of next node
           p->left=addnode(p->left, num);
           p->left->parent=p;
        }
       return p;
}

struct btreenode *makebtree(int *A, int length)
{
    struct btreenode *temp=btralloc();
    int i;
    for(i=0; i<=length;i++)
    {
        addnode(temp,A[i]);
    }
    return temp;
}
//in order tree walk
void treeprint(struct btreenode *p)
{
    if (p != NULL)
    {  
        treeprint(p->left);
        printf("%d\n", p->key);
        treeprint(p->right);
    }
        
}
//preorder tree print
void preordertreeprint(struct btreenode *p)
{
    if (p != NULL)
    {
        printf("%d\n",p->key);
        preordertreeprint(p->left);
        preordertreeprint(p->right);
    }
}
//postorder tree  print
void postordertreeprint(struct btreenode *p)
{
    if (p != NULL)
    {
        postordertreeprint(p->left);
        postordertreeprint(p->right);
        printf("%d\n",p->key);
    }
}
//iterative tree search
struct btreenode *itertreesearch(struct btreenode *x, int k)
{
    while (x != NULL && k !=(x->key))
    {
        if (k<(x->key)) x= x->left;
        else x= x->right;
    }
    return x;
}   

int main()
{
    //init randarray
    int i,j;
    int length=20;
    int array[length];
    for(i=0;i<=length;i++)
    {
        array[i]=rand()%length;
    }
    printf("Here is the rand array\n");
    for(j=0;j<=length; j++)
    {
        printf("%d\n",array[j]);
    }
    //make a tree out of array
    struct btreenode *treearr=makebtree(array, length);
    printf("Here is the In-order walk of tree\n");
    treeprint(treearr);
    return 0;
}

Comments: my implementation of bsts follows closely the design pattern presented in Kernighan and Ritchie's classic C programming language book. The algorithms are taken from Intro to Algorithms by Cormen et al. The only thing worthy of special note is that is a randomly built bst and hence all of the standard dynamic set operations take O(log n). In the near future, I will implement variations of bsts, such as red/black trees and splay trees. I will also apply treelike structures to the common and not so common graph algorithms.

Heap: Version 1

//generic heap class based on arraylist
import java.util.ArrayList;

//extending the Comparable makes the compareTo method available
public class Heap {
  //initialize a generic arraylist instance 
  private ArrayList list = new ArrayList();

  /** Create a default heap */
  public Heap() {
  }

  /** Create a heap from an array of objects */
  public Heap(E[] objects) {
    for (int i = 0; i < objects.length; i++)
      //this add method should be called something more like heapify
      //but the class ArrayList has an add method that should be reimplemented
      //for heaps...this is following a design pattern
      add(objects[i]);
  }

  /** Add a new object into the heap */
  public void add(E newObject) {
    list.add(newObject); // Append to the heap
    int currentIndex = list.size() - 1; // The index of the last node
    //this while loop heapifies the new array.
    while (currentIndex > 0) {
      int parentIndex = (currentIndex - 1) / 2;
      // Swap if the current object is greater than its parent
      if (list.get(currentIndex).compareTo(
          list.get(parentIndex)) > 0) {
        E temp = list.get(currentIndex);
        list.set(currentIndex, list.get(parentIndex));
        list.set(parentIndex, temp);
      }
      else
        break; // the tree is a heap now

      currentIndex = parentIndex;
    }
  }

  /** Remove the root from the heap */
  public E remove() {
    if (list.size() == 0) return null;
    //return root of heap 
    E removedObject = list.get(0);
    list.set(0, list.get(list.size() - 1));
    //make list 1 element smaller
    list.remove(list.size() - 1);
    
    //while loop to heapify the new array
    int currentIndex = 0;
    while (currentIndex < list.size()) {
      int leftChildIndex = 2 * currentIndex + 1;
      int rightChildIndex = 2 * currentIndex + 2;

      // Find the maximum between two children
      if (leftChildIndex >= list.size()) break; // The tree is a heap
      int maxIndex = leftChildIndex;
      if (rightChildIndex < list.size()) {
        if (list.get(maxIndex).compareTo(
            list.get(rightChildIndex)) < 0) {
          maxIndex = rightChildIndex;
        }
      }

      // Swap if the current node is less than the maximum
      if (list.get(currentIndex).compareTo(
          list.get(maxIndex)) < 0) {
        E temp = list.get(maxIndex);
        list.set(maxIndex, list.get(currentIndex));
        list.set(currentIndex, temp);
        currentIndex = maxIndex;
      }
      else
        break; // The tree is a heap
    }

    return removedObject;
  }

  /** Get the number of nodes in the tree */
  public int getSize() {
    return list.size();
  }
}

EDIT: line 4 is not rendering correctly. sorry. :(
Comments: Because heaps a binary tree most of the basic dynamic set operations can be implemented on a heap in O(log n), or in time that is at worst the height of the heap. In fact, the reason why the above code works is due to the fact that we are interacting with an array as a heap. Application #1: Sorting

 
/** Heap sort method */
  public static  void heapSort(E[] list) {
    // Create a Heap of integers
    Heap heap = new Heap();

    // Add elements to the heap
    for (int i = 0; i < list.length; i++)
      heap.add(list[i]);

    // Remove elements from the heap
    for (int i = list.length - 1; i >= 0; i--)
      list[i] = heap.remove();
  }
  
  /** A test method */
  public static void main(String[] args) {
    Integer[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
    heapSort(list);
    for (int i = 0; i < list.length; i++)
      System.out.print(list[i] + " ");
  }
}

EDIT: line 2 of Heapsort is not rendering correctly. Sorry.

 Comments: Sorting with a heap is probably the easiest application of the heap. In the near future I will apply heaps to different problems. Also, I will implement variations of heaps like the binomial heap, Fibonacci heap, and soft heap.