001: import java.util.*;
002: 
003: /**
004:    This class implements a heap.
005: */
006: public class MinHeap
007: {
008:    /**
009:       Constructs an empty heap.
010:    */
011:    public MinHeap()
012:    {
013:       elements = new ArrayList<Comparable>();
014:       elements.add(null); 
015:    }
016: 
017:    /**
018:       Adds a new element to this heap.
019:       @param newElement the element to add
020:    */
021:    public void add(Comparable newElement)
022:    {
023:       // Add a new leaf
024:       elements.add(null);
025:       int index = elements.size() - 1;
026:       
027:       // Demote parents that are larger than the new element
028:       while (index > 1 
029:             && getParent(index).compareTo(newElement) > 0) 
030:       {
031:          elements.set(index, getParent(index));
032:          index = getParentIndex(index);
033:       }
034: 
035:       // Store the new element into the vacant slot
036:       elements.set(index, newElement);
037:    }
038: 
039:    /**
040:       Gets the minimum element stored in this heap.
041:       @return the minimum element
042:    */
043:    public Comparable peek()
044:    {
045:       return elements.get(1);
046:    }
047: 
048:    /**
049:       Removes the minimum element from this heap.
050:       @return the minimum element
051:    */
052:    public Comparable remove()
053:    {
054:       Comparable minimum = elements.get(1);      
055: 
056:       // Remove last element
057:       int lastIndex = elements.size() - 1;
058:       Comparable last = elements.remove(lastIndex);
059: 
060:       if (lastIndex > 1)
061:       {
062:          elements.set(1, last);
063:          fixHeap();     
064:       }
065: 
066:       return minimum;
067:    }
068: 
069:    /**
070:       Turns the tree back into a heap, provided only the root 
071:       node violates the heap condition.
072:    */
073:    private void fixHeap()
074:    {
075:       Comparable root = elements.get(1);
076: 
077:       int lastIndex = elements.size() - 1;
078:       // Promote children of removed root while they are larger than last      
079: 
080:       int index = 1;
081:       boolean more = true;
082:       while (more)
083:       {
084:          int childIndex = getLeftChildIndex(index);
085:          if (childIndex <= lastIndex)
086:          {
087:             // Get smaller child 
088: 
089:             // Get left child first
090:             Comparable child = getLeftChild(index);
091: 
092:             // Use right child instead if it is smaller
093:             if (getRightChildIndex(index) <= lastIndex 
094:                   && getRightChild(index).compareTo(child) < 0)
095:             {
096:                childIndex = getRightChildIndex(index);
097:                child = getRightChild(index);
098:             }
099: 
100:             // Check if larger child is smaller than root
101:             if (child.compareTo(root) < 0) 
102:             {
103:                // Promote child
104:                elements.set(index, child);
105:                index = childIndex;
106:             }
107:             else
108:             {
109:                // Root is smaller than both children
110:                more = false;
111:             }
112:          }
113:          else 
114:          {
115:             // No children
116:             more = false; 
117:          }
118:       }
119: 
120:       // Store root element in vacant slot
121:       elements.set(index, root);
122:    }
123: 
124:    /**
125:       Returns the number of elements in this heap.
126:    */
127:    public int size()
128:    {
129:       return elements.size() - 1;
130:    }
131: 
132:    /**
133:       Returns the index of the left child.
134:       @param index the index of a node in this heap
135:       @return the index of the left child of the given node
136:    */
137:    private static int getLeftChildIndex(int index)
138:    {
139:       return 2 * index;
140:    }
141: 
142:    /**
143:       Returns the index of the right child.
144:       @param index the index of a node in this heap
145:       @return the index of the right child of the given node
146:    */
147:    private static int getRightChildIndex(int index)
148:    {
149:       return 2 * index + 1;
150:    }
151: 
152:    /**
153:       Returns the index of the parent.
154:       @param index the index of a node in this heap
155:       @return the index of the parent of the given node
156:    */
157:    private static int getParentIndex(int index)
158:    {
159:       return index / 2;
160:    }
161: 
162:    /**
163:       Returns the value of the left child.
164:       @param index the index of a node in this heap
165:       @return the value of the left child of the given node
166:    */
167:    private Comparable getLeftChild(int index)
168:    {
169:       return elements.get(2 * index);
170:    }
171: 
172:    /**
173:       Returns the value of the right child.
174:       @param index the index of a node in this heap
175:       @return the value of the right child of the given node
176:    */
177:    private Comparable getRightChild(int index)
178:    {
179:       return elements.get(2 * index + 1);
180:    }
181: 
182:    /**
183:       Returns the value of the parent.
184:       @param index the index of a node in this heap
185:       @return the value of the parent of the given node
186:    */
187:    private Comparable getParent(int index)
188:    {
189:       return elements.get(index / 2);
190:    }
191: 
192:    private ArrayList<Comparable> elements;
193: }