| 1 | {Heap} = require '..'
|
| 2 | {random} = Math
|
| 3 |
|
| 4 | describe 'Heap#push, Heap#pop', ->
|
| 5 | it 'should sort an array using push and pop', ->
|
| 6 | heap = new Heap
|
| 7 | heap.push(random()) for i in [1..10]
|
| 8 | sorted = (heap.pop() until heap.empty())
|
| 9 | sorted.slice().sort().should.eql(sorted)
|
| 10 |
|
| 11 | it 'should work with custom comparison function', ->
|
| 12 | cmp = (a, b) ->
|
| 13 | return -1 if a > b
|
| 14 | return 1 if a < b
|
| 15 | 0
|
| 16 | heap = new Heap(cmp)
|
| 17 | heap.push(random()) for i in [1..10]
|
| 18 | sorted = (heap.pop() until heap.empty())
|
| 19 | sorted.slice().sort().reverse().should.eql(sorted)
|
| 20 |
|
| 21 | describe 'Heap#replace', ->
|
| 22 | it 'should behave like pop() followed by push()', ->
|
| 23 | heap = new Heap
|
| 24 | heap.push(v) for v in [1..5]
|
| 25 | heap.replace(3).should.eql(1)
|
| 26 | heap.toArray().sort().should.eql([2,3,3,4,5])
|
| 27 |
|
| 28 | describe 'Heap#pushpop', ->
|
| 29 | it 'should behave like push() followed by pop()', ->
|
| 30 | heap = new Heap
|
| 31 | heap.push(v) for v in [1..5]
|
| 32 | heap.pushpop(6).should.eql(1)
|
| 33 | heap.toArray().sort().should.eql([2..6])
|
| 34 |
|
| 35 | describe 'Heap.nsmallest', ->
|
| 36 | it 'should return exactly n elements when size() >= n', ->
|
| 37 | Heap.nsmallest(3, [1..10]).should.eql([1..3])
|
| 38 |
|
| 39 | it 'should return size() elements when size() <= n', ->
|
| 40 | Heap.nsmallest(10, [3..1]).should.eql([1..3])
|
| 41 |
|
| 42 | describe 'Heap.nlargest', ->
|
| 43 | it 'should return exactly n elements when size() >= n', ->
|
| 44 | Heap.nlargest(3, [1..10]).should.eql([10..8])
|
| 45 |
|
| 46 | it 'should return size() elements when size() <= n', ->
|
| 47 | Heap.nlargest(10, [3..1]).should.eql([3..1])
|