Heaps Project

This project contains a skeleton for you to implement a max heap. This is a test-driven project. Run the tests and read the top-most error. If it's not clear what is failing, open the test/test.js file to figure out what the test is expecting. Make the top-most test pass.

Keep making the top-most test pass until all tests pass.

Instructions

· cd into the project folder

· npm install to install dependencies in the project root directory

· npm test to run the specs

· You can view the test cases in test/test.js. Your job is to write code in

o lib/max_heap.js to implement the MaxHeap class

o lib/is_heap.js to implement the isMaxHeap function

o lib/leet_code_215.js to implement the findKthLargest function located at https://leetcode.com/problems/kth-largest-element-in-an-array/

/**

 * @param {number[]} nums

 * @param {number} k

 * @return {number}

 */

let findKthLargest = function(nums, k) {

};

Soln:--------------------------------------------------------------

// you may assume that the array will always have a null element at the 0-th index

function isMaxHeap( array ) {

// check if the tree is complete, i.e. there are no gaps like [null, 50, undefined, 20]

let isComplete = array.every( el => el !== undefined );

return isComplete && _isMaxHeap( array );

}

function _isMaxHeap( array, idx = 1 ) {

if ( array[ idx ] === undefined ) return true;

let leftIdx = 2 * idx;

let rightIdx = 2 * idx + 1;

let leftVal;

if ( array[ leftIdx ] === undefined ) {

        leftVal = -Infinity;

    } else {

        leftVal = array[ leftIdx ];

    }

let rightVal;

if ( array[ rightIdx ] === undefined ) {

        rightVal = -Infinity;

    } else {

        rightVal = array[ rightIdx ];

    }

return array[ idx ] > leftVal && array[ idx ] > rightVal &&

        _isMaxHeap( array, leftIdx ) && _isMaxHeap( array, rightIdx );

}

module.exports = {

    isMaxHeap

};

--------------------------------------------------------------------------------------------------------

class MaxHeap {

    constructor() {

this.array = [null];

    }

    getParent(idx) {

return Math.floor(idx / 2);

    }

    getLeftChild(idx) {

return idx * 2;

    }

    getRightChild(idx) {

return idx * 2 + 1;

    }

    insert(val) {

this.array.push(val);

this.siftUp(this.array.length - 1);

    }

    siftUp(idx) {

if (idx === 1) return;

let parentIdx = this.getParent(idx);

if (this.array[parentIdx] < this.array[idx]) {

            [ this.array[parentIdx], this.array[idx] ] = [ this.array[idx], this.array[parentIdx] ];

this.siftUp(parentIdx);

        }

    }

    deleteMax() {

if (this.array.length === 2) return this.array.pop();

if (this.array.length === 1) return null;

let max = this.array[1];

this.array[1] = this.array.pop();

this.siftDown(1);

return max;

    }

    siftDown(idx) {

let ary = this.array;

let leftIdx = this.getLeftChild(idx);

let rightIdx = this.getRightChild(idx); 

let leftVal = ary[leftIdx];

let rightVal = ary[rightIdx];

if (leftVal === undefined) leftVal = -Infinity;

if (rightVal === undefined) rightVal = -Infinity;

if (ary[idx] > leftVal && ary[idx] > rightVal) return;

if (leftVal < rightVal) {

var swapIdx = rightIdx;

        } else {

var swapIdx = leftIdx;

        }

        [ ary[idx], ary[swapIdx] ] = [ ary[swapIdx], ary[idx] ];

this.siftDown(swapIdx);

    }

}

module.exports = {

    MaxHeap

};