class MaxHeap
1: //MaxHeap.java
3: class MaxHeap
4: {
5: private int[] heapArray;
6: private int heapSize;
8: public MaxHeap()
9: {
10: heapArray = new int[2];
11: heapSize = 0;
12: }
14: private void resizeArray()
15: {
16: int newLength = heapArray.length * 2;
17: int[] newArray = new int[newLength];
18: if (newArray != null)
19: {
20: // Copy from existing array to new array
21: for (int i = 0; i < heapArray.length; i++)
22: {
23: newArray[i] = heapArray[i];
24: }
26: // Set the reference to the new array
27: heapArray = newArray;
28: }
29: }
31: private void percolateUp(int nodeIndex)
32: {
33: while (nodeIndex > 0)
34: {
35: // Compute the parent node's index
36: int parentIndex = (nodeIndex - 1) / 2;
38: // Check for a violation of the max heap property
39: if (heapArray[nodeIndex] <= heapArray[parentIndex])
40: {
41: // No violation, so percolate up is done.
42: return;
43: }
44: else
45: {
46: // Swap heapArray[nodeIndex] and heapArray[parentIndex]
47: System.out.printf
48: (
49: " percolateUp() swap: %d <-> %d\n",
50: heapArray[parentIndex],
51: heapArray[nodeIndex]
52: );
53: int temp = heapArray[nodeIndex];
54: heapArray[nodeIndex] = heapArray[parentIndex];
55: heapArray[parentIndex] = temp;
57: // Continue the loop from the parent node
58: nodeIndex = parentIndex;
59: }
60: }
61: }
63: private void percolateDown(int nodeIndex)
64: {
65: int childIndex = 2 * nodeIndex + 1;
66: int value = heapArray[nodeIndex];
68: while (childIndex < heapSize)
69: {
70: // Find the max among the node and all the node's children
71: int maxValue = value;
72: int maxIndex = -1;
73: int i = 0;
74: while (i < 2 && i + childIndex < heapSize)
75: {
76: if (heapArray[i + childIndex] > maxValue)
77: {
78: maxValue = heapArray[i + childIndex];
79: maxIndex = i + childIndex;
80: }
81: i++;
82: }
84: // Check for a violation of the max heap property
85: if (maxValue == value)
86: {
87: return;
88: }
89: else
90: {
91: // Swap heapArray[nodeIndex] and heapArray[maxIndex]
92: System.out.printf
93: (
94: " percolateDown() swap: %d <-> %d\n",
95: heapArray[nodeIndex],
96: heapArray[maxIndex]
97: );
98: int temp = heapArray[nodeIndex];
99: heapArray[nodeIndex] = heapArray[maxIndex];
100: heapArray[maxIndex] = temp;
102: // Continue loop from the max index node
103: nodeIndex = maxIndex;
104: childIndex = 2 * nodeIndex + 1;
105: }
106: }
107: }
109: public void insert(int value)
110: {
111: // Resize if needed
112: if (heapSize == heapArray.length)
113: {
114: resizeArray();
115: }
117: // Add the new value to the end of the array
118: System.out.printf("insert(%d):\n", value);
119: heapArray[heapSize] = value;
120: heapSize++;
122: // Percolate up from the last index to restore heap property.
123: percolateUp(heapSize - 1);
124: }
126: public int remove()
127: {
128: // Save the max value from the root of the heap.
129: System.out.println("remove():");
130: int maxValue = heapArray[0];
132: // Move the last item in the array into index 0.
133: int replaceValue = heapArray[heapSize - 1];
134: heapSize--;
135: if (heapSize > 0)
136: {
137: heapArray[0] = replaceValue;
139: // Percolate down to restore max heap property.
140: percolateDown(0);
141: }
143: // Return the max value
144: return maxValue;
145: }
147: public String getHeapArrayString()
148: {
149: if (heapSize == 0)
150: {
151: return "[]";
152: }
154: String arrayString = String.format("[%d", heapArray[0]);
155: for (int i = 1; i < heapSize; i++)
156: {
157: arrayString += (", " + heapArray[i]);
158: }
159: return arrayString + "]";
160: }
162: public int getHeapSize()
163: {
164: return heapSize;
165: }
166: }