1. |
function exchange(pos1,pos2){ |
2. |
var temp
= a[pos1]; |
3. |
a[pos1]
= a[pos2]; |
4. |
a[pos2]
= temp; |
5. |
} |
6. |
|
7. |
function parent(i){ |
8. |
return i%2?((i
- i%2)/2):(i/2
- 1); |
9. |
} |
10. |
|
11. |
function leftChild(i){ |
12. |
return
2*i
+ 1; |
13. |
} |
14. |
|
15. |
function rightChild(i){ |
16. |
return
2*i
+ 2; |
17. |
} |
18. |
|
19. |
function maxHeapify(A, i){ |
20. |
var largest; |
21. |
var left
= leftChild(i), |
22. |
right
= rightChild(i); |
23. |
if(left
<= heapSize && A[left]
> A[i]) |
24. |
largest
= left; |
25. |
else largest
= i; |
26. |
if(right
<= heapSize && A[right]
> A[largest]) |
27. |
largest = right; |
28. |
if(largest
!= i){ |
29. |
exchange(i,largest); |
30. |
maxHeapify(A,largest); |
31. |
} |
32. |
} |
33. |
|
34. |
function buildMaxHeap(A){ |
35. |
heapSize
= A.length -
1; |
36. |
var mid
= (heapSize - heapSize%2)/2; |
37. |
for(var i
= mid; i >
0; i--) |
38. |
maxHeapify(A, i); |
39. |
} |
40. |
|
41. |
function heapSort(A){ |
42. |
buildMaxHeap(A); |
43. |
for(var i
= A.length -
1; i >
0; i--){ |
44. |
exchange(0,i); |
45. |
heapSize
-= 1; |
46. |
maxHeapify(A,0); |
47. |
} |
48. |
} |