00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
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
00091 isHeap = true;
00092 }
00093
00094
00095 public static void main(String args[])
00096 {
00097 Vector v = new Vector();
00098 MinHeap h = new MinHeap();
00099
00100
00101
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
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
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
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 }