Commitce13ff2

authored

Merge pull requestmgechev#100 from krzysztof-grzybek/master

Fix heap

2 parents0ecc151 +c822875 commitce13ff2Copy full SHA for ce13ff2

File tree

+37

-1

lines changed

+37

-1

lines changed

Lines changed: 3 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -82,7 +82,8 @@`
`82`	`82`	`}`
`83`	`83`
`84`	`84`	`if(right<this._heap.length&&`
`85`		`-this._cmp(this._heap[right],this._heap[index])>0){`
	`85`	`+this._cmp(this._heap[right],this._heap[index])>0&&`
	`86`	`+this._cmp(this._heap[right],this._heap[left])>0){`
`86`	`87`	`extr=right;`
`87`	`88`	`}`
`88`	`89`
`@@ -116,6 +117,7 @@`
`116`	`117`	`index=parent;`
`117`	`118`	`parent=Math.floor(parent/2);`
`118`	`119`	`}`
	`120`	`+this._heapify(index);`
`119`	`121`	`}`
`120`	`122`	`returnparent;`
`121`	`123`	`};`

Lines changed: 34 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -58,4 +58,38 @@ describe('Heap', function () {`
`58`	`58`	`res=heap.extract();`
`59`	`59`	`expect(res).toBe(66);`
`60`	`60`	`});`
	`61`	`+it('should update top node properly',function(){`
	`62`	`+varheap=newHeap(function(a,b){`
	`63`	`+returna.val-b.val;`
	`64`	`+});`
	`65`	`+varobjectToUpdate={val:66};`
	`66`	`+heap.add(objectToUpdate);`
	`67`	`+heap.add({val:11});`
	`68`	`+heap.add({val:55});`
	`69`	`+objectToUpdate.val=0;`
	`70`	`+heap.update(objectToUpdate);`
	`71`	`+varres=heap.extract();`
	`72`	`+expect(res.val).toBe(55);`
	`73`	`+res=heap.extract();`
	`74`	`+expect(res.val).toBe(11);`
	`75`	`+res=heap.extract();`
	`76`	`+expect(res.val).toBe(0);`
	`77`	`+});`
	`78`	`+it('should update bottom node properly',function(){`
	`79`	`+varheap=newHeap(function(a,b){`
	`80`	`+returna.val-b.val;`
	`81`	`+});`
	`82`	`+varobjectToUpdate={val:0};`
	`83`	`+heap.add(objectToUpdate);`
	`84`	`+heap.add({val:11});`
	`85`	`+heap.add({val:55});`
	`86`	`+objectToUpdate.val=66;`
	`87`	`+heap.update(objectToUpdate);`
	`88`	`+varres=heap.extract();`
	`89`	`+expect(res.val).toBe(66);`
	`90`	`+res=heap.extract();`
	`91`	`+expect(res.val).toBe(55);`
	`92`	`+res=heap.extract();`
	`93`	`+expect(res.val).toBe(11);`
	`94`	`+});`
`61`	`95`	`});`

Comments

(0)