1 <html>
2 <head>
3 <script language="JavaScript">
4 <!--hide
5 // javascript.heapsort.html
6 // Javascript Heapsort
7 // author: John Bryan, Jr.
8 // September 22, 2006
9 function ConstructHeap(integers)
10 {
11 N=integers.length
12 r=N
13 for (i=N-1; i>=0; i--)
14 {
15 integers=Bubbledown(integers,i,r)
16 }
17 return integers
18 }
19 function Bubbledown(integers,i,r)
20 {
21 N=r
22 j=i
23 while(1)
24 {
25 k=j
26 if(((2*k+1)<N)&&(integers[2*k+1]>integers[j]))
27 j=2*k+1
28 if(((2*k+2)<N)&&(integers[2*k+2]>integers[j]))
29 j=2*k+2
30 integers=Swap(integers,k,j)
31 if (k==j) {break}
32 }
33 return integers
34 }
35 function Heapsort(integers)
36 {
37 N=integers.length
38 for (r=N-1; r>0; r--)
39 {
40 k=r;
41 j=0;
42 integers=Swap(integers,k,j);
43 i=0;
44 N=r;
45 integers=Bubbledown(integers,i,r);
46 }
47 return integers
48 }
49 function Swap(integers,k,j)
50 {
51 temp = integers[k];
52 integers[k] = integers[j];
53 integers[j] = temp;
54 return integers;
55 }
56
57 function Get_Random_Integer(number)
58 {
59 var integers = new Array()
60 for (var i=0;i<number;i++)
61 {
62 integers[i]= Math.floor(Math.random()*100)
63 document.write(integers[i] + " ")
64 if((i+1)%10==0){document.write("<br />")}
65 }
66 return integers;
67 }
68 function Write_Sorted_Integers(integers)
69 {
70 document.write("<br />" + "<br />" + "The sorted integers are " + "<br />")
71 for (var i=0;i<integers.length;i++)
72 {
73 document.write(integers[i] + " ")
74 if((i+1)%10==0){document.write("<br />")}
75 }
76 }
77
78 function Get_Integers(integers)
79 {
80 var integer_string = new Array()
81 integer_string=prompt('Please enter integers, each separated by a space, to sort, or enter a single integer to sort that number of random integers.', ' ')
82 integers = integer_string.split(" ")
83 N = integers.length
84 for (i=0;i<N;i++)
85 {
86 integers[i] = parseInt(integers[i])
87 }
88 if (N==1)
89 {
90 document.write(integers + " random numbers will be sorted." + "<br />")
91 document.writeln("The random numbers to be sorted are" + "<br />")
92 integers=Get_Random_Integer(integers)
93 }
94 return integers
95 }
96
97 //-->
98
99 </script>
100 </head>
101
102 <body>
103 <script language="JavaScript">
104 <!--hide
105 var integers = new Array()
106 integers=Get_Integers(integers)
107 integers=ConstructHeap(integers)
108 integers=Heapsort(integers)
109 Write_Sorted_Integers(integers)
110 //-->
111 </script>
112 </body>
113 </html>