3
\$\begingroup\$

As part of my study on fundamentals, I have implemented the following code in JavaScript for a MinHeap data structure.

Please have a look and I look forward to your feedback for any improvements.

const swap = require('../swap');

function Heap(){
  this.heap = [];
}

Heap.prototype.getParent = function(index){
  return (index-1)/2;
}

Heap.prototype.getLeft = function(index){
  return (2*index)+1;
}

Heap.prototype.getRight = function(index){
  return (2*index)+2;
}

//inserts a new value to the min-heap
Heap.prototype.insert = function(value){
  this.heap.push(value);
  this.heapifyUp(this.heap.length-1);
  return;
}

//deletes any node at given index
Heap.prototype.delete = function(index){
  if(index === 0){
    this.heap[0] = this.heap[this.heap.length-1];
    this.heap.splice(this.heap.length-1, 1);
    this.heapifyDown(0);
    return;
  }

  this.heap[index] = this.heap[this.heap.length-1];
  this.heap.splice(this.heap.length-1, 1);
  var parent = this.getParent(index);
  (this.heap[index]<this.heap[parent])? this.heapifyUp(index) : this.heapifyDown(index);
  return;
}

//extracts min value and recalibrates minheap
Heap.prototype.extractMin = function(){
  var temp = this.heap[0];

  swap(this.heap, 0, (this.heap.length-1));
  this.heap.slice((this.heap.length-1), 1);
  this.heapifyDown(0);

  return temp;
}

//decreases the value of node at given index by given value
Heap.prototype.decrease = function(index, value){

  if((this.heap[index]-value)<0) return false;

  this.heap[index] = this.heap[index]-value;
  (index === 0) ? this.heapifyDown(0) : this.heapifyUp(index);
  return;
}


Heap.prototype.heapifyUp = function(index){

  var parent = this.getParent(index);

  while(parent>=0 && this.heap[parent]>this.heap[index]){
    swap(this.heap, parent, index);
    index = parent;
    parent = this.getParent(index);
  }

}

Heap.prototype.heapifyDown = function(index){

  var left = this.getLeft(index);
  var right = this.getRight(index);

  while(this.heap[index]>this.heap[left] || this.heap[index]>this.heap[right]){
    if(this.heap[index]>this.heap[left]){
      swap(this.heap, left, index);
      index = left;
      left = this.getLeft(index);
    }
    if(this.heap[index]>this.heap[right]){
      swap(this.heap, right, index);
      index = right;
      right = this.getLeft(index);
    }
  }

}

\$\endgroup\$
5
  • \$\begingroup\$ bug in delete(0): duplicates the item that is last in the array. You're missing the splice to shorten the array. \$\endgroup\$
    – Snowbody
    Commented Dec 16, 2017 at 1:40
  • \$\begingroup\$ bug in decrease() it allows negative values, which cause the item to be increased in value, whic breaks up the heap property \$\endgroup\$
    – Snowbody
    Commented Dec 16, 2017 at 1:45
  • \$\begingroup\$ I had to roll back your edit. You're not allowed to edit the code after you initially post, per the rules of your site. If you want the new code reviewed, post a new question, and post links between each of them. \$\endgroup\$
    – Snowbody
    Commented Dec 16, 2017 at 2:18
  • \$\begingroup\$ @Snowbody Just keep the edit. Broken code is off-topic anyway and codereview.meta.stackexchange.com/questions/5688/… suggests that editing before the first answer is still acceptable \$\endgroup\$
    – le_m
    Commented Dec 16, 2017 at 2:27
  • \$\begingroup\$ Okay @le_m the fixed version is back. \$\endgroup\$
    – Snowbody
    Commented Dec 16, 2017 at 2:30

2 Answers 2

3
\$\begingroup\$

The code seems good to me. You have one bug and some unnecessary code.

  • First of all, it's not clear what types of values can be stored in the heap. It looks like it's supposed to be positive numbers, but the only place you check for this is in the decrease-key function. But there's actually not anything stopping callers from attempting to store strings, negative numbers, classes, etc. This will lead to bizarre behavior. I think you need to validate the input and make sure only the right type of data is going in.
  • It's not necessary to end your functions with return
  • The line

    (this.heap[index]<this.heap[parent])? this.heapifyUp(index) : this.heapifyDown(index);
    

    should be written as a normal if, not a ternary.

  • This line

    this.heap.slice((this.heap.length-1), 1);
    

    is repeated several times; perhaps it should be brought into its own helper method with an explanatory name (suggest deleteLastElement()).

  • In extractMin(), this line:

    swap(this.heap, 0, (this.heap.length-1));
    

    performs unnecessary work. The last element is about to be deleted, so you don't need to put anything there. Just say

    this.heap[0]=this.heap[this.heap.length-1]`
    
  • A conceptual problem is that you only allow accessing nodes by index. How is someone using your code supposed to know what the index is? An item could move around the heap a lot due to inserts and removals and heapify calls. This applies to decrease() and delete()

  • heapifyDown() has a bug. Consider the heap represented by [4,6,5,7] and what happens if you extractMin().
  • decreaseKey() has a bug, but I'm not going to find this one for you.
\$\endgroup\$
1
  • \$\begingroup\$ Thanks @Snowbody! I'll correct these issues and post as a new question. \$\endgroup\$ Commented Dec 16, 2017 at 8:46
2
\$\begingroup\$

One other aspect I noticed is that the swap inclusion line uses the const statement. You could use const and let where appropriate. For example, in the method delete(), this line:

var parent = this.getParent(index);

Could use const, since there appears to be no re-assignment.

const parent = this.getParent(index);
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.