1// heapsort 2 3function 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 15function 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 26function 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 41function 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} 54