Few more algorithms are documented. MaxHeap is added

mgechev · mgechev · commit aee4840b1f39 · 2012-12-02T12:15:39.000+02:00
diff --git a/src/data-structures/heap.js b/src/data-structures/heap.js
@@ -0,0 +1,99 @@
+/**
+ * Constructor function of maximum heap
+ *
+ * @public
+ */
+function MaxHeap() {
+    this._heap = [];
+}
+
+/**
+ * Exchange indexes with start index given as argument
+ * to turn the heap into valid maxheap. On a single call
+ * this method maintains only a single "branch" of the heap
+ *
+ * @private
+ * @param {number} index The parent
+ */
+MaxHeap.prototype._heapify = function (index) {
+    var max = index,
+        left = 2 * index + 1,
+        right = 2 * index + 2,
+        temp;
+
+    if (left < this._heap.length && this._heap[left] > this._heap[index])
+        max = left;
+
+    if (right < this._heap.length && this._heap[right] > this._heap[index])
+        max = right;
+
+    if (index !== max) {
+        temp = this._heap[index];
+        this._heap[index] = this._heap[max];
+        this._heap[max] = temp;
+        this._heapify(max);
+    }
+
+}
+
+/**
+ * Increases the key for give index
+ *
+ * @public
+ * @param {number} index Index which key should be increased
+ * @param {number} value New value of the key
+ * @returns {number} parent The new position of the element
+ */
+MaxHeap.prototype.increaseKey = function (index, value) {
+    var elem = this._heap[index],
+        parent = Math.floor(index / 2),
+        temp;
+    if (elem && elem <= value) {
+        while (parent >= 0 && elem > this._heap[parent]) {
+            temp = this._heap[parent];
+            this._heap[parent] = elem;
+            this._heap[index] = temp; 
+            index = parent;
+            parent = Math.floor(parent / 2);
+        }
+    }
+    return parent;
+}
+
+/**
+ * Adds new element to the heap
+ *
+ * @public
+ * @param {number} value The new value which will be inserted
+ * @returns {number}  The index of the inserted value
+ */
+MaxHeap.prototype.add = function (value) {
+    this._heap.push(value);
+    return this.increaseKey(this._heap.length - 1, value);
+}
+
+/**
+ * Gets the current value which is on the top of the heap
+ *
+ * @public
+ * returns {numner}  The current largest value which is on the top of the heap
+ */
+MaxHeap.prototype.max = function () {
+    return this._heap[0];
+}
+
+/**
+ * Remove and return the current maximum value which is on the top of the heap
+ *
+ * @public
+ * @returns {number} max Extracted value
+ */
+MaxHeap.prototype.extractMax = function () {
+    if (!this._heap.length)
+        throw new 'The heap is already empty!';
+
+    var max = this._heap.shift();
+    this._heapify(0);
+    return max;
+}
+
diff --git a/src/searching/binarysearch.js b/src/searching/binarysearch.js
@@ -1,5 +1,14 @@
 var array = [5, 8, 53, 56, 123, 322, 400, 2356, 8000, 23333];
 
+/**
+ * Searchs for specific element in given array using the binary search algorithm.
+ * It's complexity is O(log n)
+ *
+ * @public
+ * @param {array} array Input array
+ * @param {number} key The key of the element which index we should find
+ * @returns {number} index The index of the element or -1 if not found
+ */
 function binarySearch(array, key) {
     var middle = Math.round(array.length / 2),
         left = 0,
diff --git a/src/searching/recursive-binary-search.js b/src/searching/recursive-binary-search.js
diff --git a/src/searching/recursive-binarysearch.js b/src/searching/recursive-binarysearch.js
@@ -0,0 +1,60 @@
+var array = [5, 8, 53, 56, 123, 322, 400, 2356, 8000, 23333];
+
+
+/**
+ * Recursive version of binary search. It's complexity is O(log n).
+ *
+ * @public
+ */
+var binarySearch = (function () {
+   
+    /**
+     * Binary search.
+     *
+     * @pivate
+     * @param {array} array Given array where we should find the index of the element
+     * @param {number} key Key of the element which index should be found
+     * @param {number} left Left index
+     * @param {number} right Right index
+     * @returns {number} index The index of the element or -1 if not found
+     *
+     */ 
+    function recursiveBinarySearch(array, key, left, right) {
+        if (left > right)
+            return -1;
+        var middle = Math.floor((right + left) / 2);
+        if (array[middle] === key)
+            return middle;
+        else if (array[middle] > key) 
+            return recursiveBinarySearch(array, key, left, middle - 1);
+        else
+            return recursiveBinarySearch(array, key, middle + 1, right);
+    }
+
+    /**
+     * Calls the binary search function with it's initial values.
+     *
+     * @param {array} array The input array
+     * @param {number} key The key of the element which index should be found
+     * @returns {number} index The index of the element or -1 if not found
+     */
+    return function (array, key) {
+        return recursiveBinarySearch(array, key, 0, array.length);
+    }
+
+}());
+
+
+
+console.log(array);
+console.log(5, binarySearch(array, 5));
+console.log(8, binarySearch(array, 8));
+console.log(53, binarySearch(array, 53));
+console.log(56, binarySearch(array, 56));
+console.log(123, binarySearch(array, 123));
+console.log(322, binarySearch(array, 322));
+console.log(400, binarySearch(array, 400));
+console.log(2356, binarySearch(array, 2356));
+console.log(8000, binarySearch(array, 8000));
+console.log(8001, binarySearch(array, 8001));
+console.log(23333, binarySearch(array, 23333));
