Main Page   Packages   Class Hierarchy   Compound List   File List   Compound Members  

MinHeap.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 
00035 public class MinHeap extends Heap
00036 {
00040     public MinHeap()
00041     {
00042         super();
00043     }
00044 
00050     public MinHeap(Comparator c)
00051     {
00052         super(c);
00053     }
00054 
00058     public MinHeap(int capacity)
00059     {
00060         super(capacity);
00061     }
00062 
00067     public MinHeap(Collection c)
00068     {
00069         super(c);
00070     }
00071 
00075     public Object deleteMin()
00076     {
00077         return remove(0);
00078     }
00079 
00086     public void sort()
00087     {
00088         super.sort();
00089 
00090         // this just so happens to maintain the min-heap property
00091         isHeap = true;
00092     }
00093 
00094     // Simple test program
00095     public static void main(String args[])
00096     {
00097         Vector v = new Vector();
00098         MinHeap h = new MinHeap();
00099 
00100         //int[] numbers = {10, 1, 6, -10, 2, 7, 6};
00101         //int[] numbers = {10, 1, 6, -10, 2, 7, 4, 4, 4};
00102         int[] n = {10, 1, 6, -10, 2, 7, 4, 4, 4, -2, 4, 4};
00103         int[][] numbers = new int[n.length][2];
00104 
00105         int n4 = 0;
00106         for(int x = 0; x < n.length; x++)
00107         {
00108             numbers[x][0] = n[x];
00109             numbers[x][1] = n[x];
00110             
00111             if(n[x] == 4)
00112                 numbers[x][1] = 40+n4++;
00113         }
00114 
00115         try
00116         {
00117             System.out.print("Adding ");
00118             //Double d = null;
00119             FeatChunk d = null;
00120             for(int x = 0; x < numbers.length; x++)
00121             {
00122                 System.out.print(numbers[x][0] + " (priority = " 
00123                                  + numbers[x][1] + "), ");
00124                 //d = new Double(numbers[x]);
00125                 
00126                 d = new FeatChunk("", numbers[x][0], numbers[x][1]);
00127                 h.add(d);
00128                 v.add(d);
00129             }
00130 
00131             System.out.println("\nCalling deleteMin: ");
00132             for(int x = 0; x < numbers.length; x++)
00133                 System.out.print(h.deleteMin() + " ");
00134 
00135             System.out.println("\nRemoving an element (this should obey the heap property): ");
00136             h.addAll(v);
00137             h.remove(d);
00138             Iterator i = h.iterator();
00139             while(i.hasNext())
00140                 System.out.print(i.next() + " ");
00141 
00142             System.out.println("\nRunning heapSort: ");
00143             //h.addAll(v);
00144             h.sort();
00145             i = h.iterator();
00146             while(i.hasNext())
00147                 System.out.print(i.next() + " ");
00148         }
00149         catch(Exception e)
00150         {
00151             e.printStackTrace();
00152         }
00153     }
00154 }

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