#include
<
iostream
>
using
namespace
std;
void
DownAdjust(
int
*
a,
int
first,
int
last)
{
int
tmp,down;
tmp
=
a[first];
for
(down
=
first
*
2
+
1
;down
<=
last;down
=
down
*
2
+
1
)
{
//
if(down<last&&a[down]>a[down+1])++down;
//
if(a[down]<tmp)a[(down-1)/2]=a[down];
if
(down
<
last
&&
a[down]
<
a[down
+
1
])
++
down;
//
down<last不可少,不然last小于N-1时会将last后面的元素考虑在内
if
(a[down]
>
tmp)a[(down
-
1
)
/
2
]
=
a[down];
else
break
;
}
a[(down
-
1
)
/
2
]
=
tmp;
}
void
HeapAdjust(
int
*
a,
int
last)
{
int
first;
for
(first
=
(last
-
1
)
/
2
;first
>=
0
;first
--
)
DownAdjust(a,first,last);
}
void
HeapSort(
int
*
a,
int
N)
{
int
i,tmp;
for
(i
=
N
-
1
;i
>=
0
;i
--
)
{
HeapAdjust(a,i);
tmp
=
a[
0
];
a[
0
]
=
a[i];
a[i]
=
tmp;
}
for
(i
=
0
;i
<
N;i
++
)
cout
<<
a[i]
<<
'
'
;
cout
<<
endl;
}
void
main()
{
int
a[]
=
{
1
,
2
,
3
,
0
,
3
,
8
,
7
}
;
//
inta[]={1,1,1};
//
inta[]={3,1,3,0};
HeapSort(a,
7
);
}
//
9'
/*
{3,2,1}
{1,2,1}
1
*/
