| 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 |