MinHeap.java.html

  1  import java.util.*;
  2  
  3  /**
  4     This class implements a heap.
  5  */
  6  public class MinHeap
  7  {
  8     private ArrayList<Comparable> elements;
  9  
 10     /**
 11        Constructs an empty heap.
 12     */
 13     public MinHeap()
 14     {
 15        elements = new ArrayList<Comparable>();
 16        elements.add(null); 
 17     }
 18  
 19     /**
 20        Adds a new element to this heap.
 21        @param newElement the element to add
 22     */
 23     public void add(Comparable newElement)
 24     {
 25        // Add a new leaf
 26        elements.add(null);
 27        int index = elements.size() - 1;
 28        
 29        // Demote parents that are larger than the new element
 30        while (index > 1 
 31              && getParent(index).compareTo(newElement) > 0) 
 32        {
 33           elements.set(index, getParent(index));
 34           index = getParentIndex(index);
 35        }
 36  
 37        // Store the new element into the vacant slot
 38        elements.set(index, newElement);
 39     }
 40  
 41     /**
 42        Gets the minimum element stored in this heap.
 43        @return the minimum element
 44     */
 45     public Comparable peek()
 46     {
 47        return elements.get(1);
 48     }
 49  
 50     /**
 51        Removes the minimum element from this heap.
 52        @return the minimum element
 53     */
 54     public Comparable remove()
 55     {
 56        Comparable minimum = elements.get(1);      
 57  
 58        // Remove last element
 59        int lastIndex = elements.size() - 1;
 60        Comparable last = elements.remove(lastIndex);
 61  
 62        if (lastIndex > 1)
 63        {
 64           elements.set(1, last);
 65           fixHeap();     
 66        }
 67  
 68        return minimum;
 69     }
 70  
 71     /**
 72        Turns the tree back into a heap, provided only the root 
 73        node violates the heap condition.
 74     */
 75     private void fixHeap()
 76     {
 77        Comparable root = elements.get(1);
 78  
 79        int lastIndex = elements.size() - 1;
 80        // Promote children of removed root while they are smaller than last      
 81  
 82        int index = 1;
 83        boolean more = true;
 84        while (more)
 85        {
 86           int childIndex = getLeftChildIndex(index);
 87           if (childIndex <= lastIndex)
 88           {
 89              // Get smaller child 
 90  
 91              // Get left child first
 92              Comparable child = getLeftChild(index);
 93  
 94              // Use right child instead if it is smaller
 95              if (getRightChildIndex(index) <= lastIndex 
 96                    && getRightChild(index).compareTo(child) < 0)
 97              {
 98                 childIndex = getRightChildIndex(index);
 99                 child = getRightChild(index);
100              }
101  
102              // Check if larger child is smaller than root
103              if (child.compareTo(root) < 0) 
104              {
105                 // Promote child
106                 elements.set(index, child);
107                 index = childIndex;
108              }
109              else
110              {
111                 // Root is smaller than both children
112                 more = false;
113              }
114           }
115           else 
116           {
117              // No children
118              more = false; 
119           }
120        }
121  
122        // Store root element in vacant slot
123        elements.set(index, root);
124     }
125  
126     /**
127        Checks whether this heap is empty.
128     */
129     public boolean empty()
130     {
131        return elements.size() == 1;
132     }
133  
134     /**
135        Returns the index of the left child.
136        @param index the index of a node in this heap
137        @return the index of the left child of the given node
138     */
139     private static int getLeftChildIndex(int index)
140     {
141        return 2 * index;
142     }
143  
144     /**
145        Returns the index of the right child.
146        @param index the index of a node in this heap
147        @return the index of the right child of the given node
148     */
149     private static int getRightChildIndex(int index)
150     {
151        return 2 * index + 1;
152     }
153  
154     /**
155        Returns the index of the parent.
156        @param index the index of a node in this heap
157        @return the index of the parent of the given node
158     */
159     private static int getParentIndex(int index)
160     {
161        return index / 2;
162     }
163  
164     /**
165        Returns the value of the left child.
166        @param index the index of a node in this heap
167        @return the value of the left child of the given node
168     */
169     private Comparable getLeftChild(int index)
170     {
171        return elements.get(2 * index);
172     }
173  
174     /**
175        Returns the value of the right child.
176        @param index the index of a node in this heap
177        @return the value of the right child of the given node
178     */
179     private Comparable getRightChild(int index)
180     {
181        return elements.get(2 * index + 1);
182     }
183  
184     /**
185        Returns the value of the parent.
186        @param index the index of a node in this heap
187        @return the value of the parent of the given node
188     */
189     private Comparable getParent(int index)
190     {
191        return elements.get(index / 2);
192     }
193  }