1 /**
  2  * @fileOverview Implementation of a min heap.  Allows a comparator 
  3  * to be provided so that the heap may contain objects that involve a 
  4  * more complex comparison.
  5  */
  6 
  7 /**
  8  * Implementation of a min heap allowing for a comparator 
  9  * to be provided so that the heap may contain objects that involve a 
 10  * more complex comparison.
 11  * <br>
 12  * This constructor constructs a MinHeap instance and takes two optional 
 13  * parameters: an array and comparator.  If the array is provided, it 
 14  * will be used as the backing store for the heap. Therefore, all 
 15  * operations on the heap will be reflected in the provided array.
 16  * Usage
 17  * @example
 18  * Sample Usage:
 19 	var heapq = new MinHeap();
 20 	heapq.push(5);
 21 	heapq.push(2);
 22 	heapq.push(1);
 23 	heapq.pop()); // returns 1
 24 	heapq.pop()); // returns 2
 25  * @param array Array to use heapify or null to start with an empty
 26  * heap.
 27  * @param comparator alternate comparator used to compare each 
 28  * item within the heap.  If not provided, the default will perform
 29  * a simple comparison on the item.
 30  *
 31  * @returns instance of MinHeap
 32  * @constructor
 33  */
 34 function MinHeap(array, comparator) {
 35 
 36     /**
 37      * Storage for heap. 
 38      * @private
 39      */
 40 	this.heap = array || new Array();
 41 
 42     /**
 43      * Default comparator used if an override is not provided.
 44      * @private
 45      */
 46 	this.compare = comparator || function(item1, item2) {
 47 		return item1 == item2 ? 0 : item1 < item2 ? -1 : 1;
 48 	};
 49 
 50     /**
 51      * Retrieve the index of the left child of the node at index i.
 52      * @private
 53      */
 54 	this.left = function(i) {
 55 		return 2 * i + 1;
 56 	};
 57     /**
 58      * Retrieve the index of the right child of the node at index i.
 59      * @private
 60      */
 61 	this.right = function(i) {
 62 		return 2 * i + 2;
 63 	};
 64     /**
 65      * Retrieve the index of the parent of the node at index i.
 66      * @private
 67      */
 68 	this.parent = function(i) {
 69 		return Math.ceil(i / 2) - 1;
 70 	};
 71 
 72     /**
 73      * Ensure that the contents of the heap don't violate the 
 74      * constraint. 
 75      * @private
 76      */
 77 	this.heapify = function(i) {
 78 		var lIdx = this.left(i);
 79 		var rIdx = this.right(i);
 80 		var smallest;
 81 		if (lIdx < this.heap.length
 82 				&& this.compare(this.heap[lIdx], this.heap[i]) < 0) {
 83 			smallest = lIdx;
 84 		} else {
 85 			smallest = i;
 86 		}
 87 		if (rIdx < this.heap.length
 88 				&& this.compare(this.heap[rIdx], this.heap[smallest]) < 0) {
 89 			smallest = rIdx;
 90 		}
 91 		if (i != smallest) {
 92 			var temp = this.heap[smallest];
 93 			this.heap[smallest] = this.heap[i];
 94 			this.heap[i] = temp;
 95 			this.heapify(smallest);
 96 		}
 97 	};
 98 
 99     /**
100      * Starting with the node at index i, move up the heap until parent value
101      * is less than the node.
102      * @private
103      */
104 	this.siftUp = function(i) {
105 		var p = this.parent(i);
106 		if (p >= 0 && this.compare(this.heap[p], this.heap[i]) > 0) {
107 			var temp = this.heap[p];
108 			this.heap[p] = this.heap[i];
109 			this.heap[i] = temp;
110 			this.siftUp(p);
111 		}
112 	};
113 
114     /**
115      * Heapify the contents of an array.
116      * This function is called when an array is provided.
117      * @private
118      */
119 	this.heapifyArray = function() {
120 		// for loop starting from floor size/2 going up and heapify each.
121 		var i = Math.floor(this.heap.length / 2) - 1;
122 		for (; i >= 0; i--) {
123 		//	jstestdriver.console.log("i: ", i);
124 			this.heapify(i);
125 		}
126 	};
127 
128 	// If an initial array was provided, then heapify the array.
129 	if (array != null) {
130 		this.heapifyArray();
131 	}
132 	;
133 }
134 
135 /**
136  * Place an item in the heap.  
137  * @param item
138  * @function
139  */
140 MinHeap.prototype.push = function(item) {
141 	this.heap.push(item);
142 	this.siftUp(this.heap.length - 1);
143 };
144 
145 /**
146  * Insert an item into the heap.
147  * @param item
148  * @function
149  */
150 MinHeap.prototype.insert = function(item) {
151     this.push(item);
152 };
153 
154 /**
155  * Pop the minimum valued item off of the heap. The heap is then updated 
156  * to float the next smallest item to the top of the heap.
157  * @returns the minimum value contained within the heap.
158  * @function
159  */
160 MinHeap.prototype.pop = function() {
161 	var value;
162 	if (this.heap.length > 1) {
163 		value = this.heap[0];
164 		// Put the bottom element at the top and let it drift down.
165 		this.heap[0] = this.heap.pop();
166 		this.heapify(0);
167 	} else {
168 		value = this.heap.pop();
169 	}
170 	return value;
171 };
172 
173 /**
174  * Remove the minimum item from the heap.
175  * @returns the minimum value contained within the heap.
176  * @function
177  */
178 MinHeap.prototype.remove = function() {
179     return this.pop();
180 };
181 
182 
183 /**
184  * Returns the minimum value contained within the heap.  This will
185  * not remove the value from the heap.
186  * @returns the minimum value within the heap.
187  * @function
188  */
189 MinHeap.prototype.getMin = function() {
190 	return this.heap[0];
191 };
192 
193 /**
194  * Return the current number of elements within the heap.
195  * @returns size of the heap.
196  * @function
197  */
198 MinHeap.prototype.size = function() {
199 	return this.heap.length;
200 };
201