OLD | NEW |
| (Empty) |
1 // heapsort | |
2 | |
3 function sort_heap(sort, end) { | |
4 if (arguments.length == 1) { | |
5 var mid = Math.floor(sort.size/2 - 1); | |
6 sort.add_work(function() { build_heap(sort, mid); }, "build_heap"); | |
7 } else if (end > 0) { | |
8 sort.swap(end, 0); | |
9 end--; | |
10 sort.add_work(function() { sort_heap(sort, end); }, "sort_heap"); | |
11 sort.add_work(function() { sift_down(sort, 0, end, 0); }, "sift_down"); | |
12 } | |
13 } | |
14 | |
15 function build_heap(sort, start) { | |
16 if (start >= 0) { | |
17 sort.add_work(function() { build_heap(sort, start-1); }, "build_heap"); | |
18 sort.add_work(function() { sift_down(sort, start, sort.size-1, start); }, | |
19 "sift_down"); | |
20 } else { | |
21 sort.add_work(function() { sort_heap(sort, sort.size-1); }, | |
22 "sort_heap"); | |
23 } | |
24 } | |
25 | |
26 function sift_down(sort, start, end, root) { | |
27 var child = root * 2 + 1; | |
28 if (child <= end) { | |
29 if (child < end && sort.compare(child, child + 1) < 0) { | |
30 child++; | |
31 } | |
32 if (sort.compare(root, child) < 0) { | |
33 sort.swap(root, child); | |
34 root = child; | |
35 sort.add_work(function() { sift_down(sort, start, end, root); }, | |
36 "sift_down"); | |
37 } | |
38 } | |
39 } | |
40 | |
41 function validate_heap(sort) { | |
42 var i = Math.floor(sort.size/2 - 1); | |
43 while (i >= 0) { | |
44 child = i * 2 + 1; | |
45 if (sort.compare(i, child) < 0) | |
46 return 0; | |
47 if (child + 1 < sort.size) | |
48 if (sort.compare(i, child + 1) < 0) | |
49 return 0; | |
50 i--; | |
51 } | |
52 return 1; | |
53 } | |
OLD | NEW |