1: import java.util.Arrays;
2: /**
3: A class that implements the ADT maxheap by using an array.
4:
5: @author Frank M. Carrano
6: @author Timothy M. Henry
7: @version 5.0
8: */
9: public final class MaxHeap<T extends Comparable<? super T>>
10: implements MaxHeapInterface<T>
11: {
12: private T[] heap; // Array of heap entries; ignore heap[0]
13: private int lastIndex; // Index of last entry and number of entries
14: private boolean integrityOK = false;
15: private static final int DEFAULT_CAPACITY = 25;
16: private static final int MAX_CAPACITY = 10000;
17:
18: public MaxHeap()
19: {
20: this(DEFAULT_CAPACITY); // Call next constructor
21: } // end default constructor
22:
23: public MaxHeap(int initialCapacity)
24: {
25: // Is initialCapacity too small?
26: if (initialCapacity < DEFAULT_CAPACITY)
27: initialCapacity = DEFAULT_CAPACITY;
28: else // Is initialCapacity too big?
29: checkCapacity(initialCapacity);
30:
31: // The cast is safe because the new array contains null entries
32: @SuppressWarnings("unchecked")
33: T[] tempHeap = (T[])new Comparable[initialCapacity + 1];
34: heap = tempHeap;
35: lastIndex = 0;
36: integrityOK = true;
37: } // end constructor
39: public void add(T newEntry)
40: {
41: // See Segment 27.8.
42: } // end add
44: public T removeMax()
45: {
46: // See Segment 27.12.
47: } // end removeMax
49: public T getMax()
50: {
51: checkIntegrity();
52: T root = null;
53: if (!isEmpty())
54: root = heap[1];
55: return root;
56: } // end getMax
58: public boolean isEmpty()
59: {
60: return lastIndex < 1;
61: } // end isEmpty
63: public int getSize()
64: {
65: return lastIndex;
66: } // end getSize
68: public void clear()
69: {
70: checkIntegrity();
71: while (lastIndex > -1)
72: {
73: heap[lastIndex] = null;
74: lastIndex--;
75: } // end while
76: lastIndex = 0;
77: } // end clear
78:
79: // Private methods
80: // . . .
81: } // end MaxHeap