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 | array = [1,3,2,1,3,4,4,2,3,4,5,1,2,3,4,5,2,1,3,4,5,6,7,2]
|
40 | Heap.nsmallest(2, array).should.eql([1, 1])
|
41 |
|
42 | it 'should return size() elements when size() <= n', ->
|
43 | Heap.nsmallest(10, [3..1]).should.eql([1..3])
|
44 |
|
45 | describe 'Heap.nlargest', ->
|
46 | it 'should return exactly n elements when size() >= n', ->
|
47 | Heap.nlargest(3, [1..10]).should.eql([10..8])
|
48 |
|
49 | it 'should return size() elements when size() <= n', ->
|
50 | Heap.nlargest(10, [3..1]).should.eql([3..1])
|