Main Page   Packages   Class Hierarchy   Compound List   File List   Compound Members  

MaxHeap.java

00001 /*
00002  *  Copyright 2006-2007 Columbia University.
00003  *
00004  *  This file is part of MEAPsoft.
00005  *
00006  *  MEAPsoft is free software; you can redistribute it and/or modify
00007  *  it under the terms of the GNU General Public License version 2 as
00008  *  published by the Free Software Foundation.
00009  *
00010  *  MEAPsoft is distributed in the hope that it will be useful, but
00011  *  WITHOUT ANY WARRANTY; without even the implied warranty of
00012  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013  *  General Public License for more details.
00014  *
00015  *  You should have received a copy of the GNU General Public License
00016  *  along with MEAPsoft; if not, write to the Free Software
00017  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
00018  *  02110-1301 USA
00019  *
00020  *  See the file "COPYING" for the text of the license.
00021  */
00022 
00023 package com.meapsoft;
00024 
00025 import java.util.Collection;
00026 import java.util.Comparator;
00027 import java.util.Iterator;
00028 import java.util.Vector;
00029 
00030 // I can't believe that the huge Java API doesn't already include such
00031 // a basic data structure
00032 
00038 public class MaxHeap extends Heap
00039 {
00043     public MaxHeap()
00044     {
00045         super();
00046     }
00047 
00053     public MaxHeap(Comparator c)
00054     {
00055         super(c);
00056     }
00057 
00061     public MaxHeap(int capacity)
00062     {
00063         super(capacity);
00064     }
00065 
00070     public MaxHeap(Collection c)
00071     {
00072         super(c);
00073     }
00074 
00078     public Object deleteMax()
00079     {
00080         return remove(0);
00081     }
00082 
00087     protected int cmp(int node1, int node2)
00088     {
00089         return -super.cmp(node1, node2);
00090     }
00091 
00092     // Simple test program
00093     public static void main(String args[])
00094     {
00095         MaxHeap h = new MaxHeap();
00096         Vector v = new Vector();
00097 
00098         //int[] numbers = {10, 1, 6, -10, 2, 7, 6};
00099         int[] numbers = {10, 1, 6, -10, 2, 7, 4};
00100 
00101         try
00102         {
00103             System.out.print("Adding ");
00104             Double d = null;
00105             for(int x = 0; x < numbers.length; x++)
00106             {
00107                 System.out.print(numbers[x] + " ");
00108                 d = new Double(numbers[x]);
00109                 h.add(d);
00110                 v.add(d);
00111             }
00112 
00113             System.out.print("\nCalling deleteMax: ");
00114             for(int x = 0; x < numbers.length; x++)
00115                 System.out.print(h.deleteMax() + " ");
00116 
00117             System.out.print("\nRemoving an element (this should obey the heap property): ");
00118             h.addAll(v);
00119             h.remove(d);
00120             Iterator i = h.iterator();
00121             while(i.hasNext())
00122                 System.out.print(i.next() + " ");
00123 
00124             System.out.print("\nRunning heapSort: ");
00125             //h.addAll(v);
00126             h.sort();
00127             i = h.iterator();
00128             while(i.hasNext())
00129                 System.out.print(i.next() + " ");
00130             System.out.print("\n");
00131         }
00132         catch(Exception e)
00133         {
00134             e.printStackTrace();
00135         }
00136     }
00137 }

Generated on Tue Feb 6 19:02:26 2007 for MEAPsoft by doxygen1.2.18