static
?
void
?_build_heap(
int
?
*
array,
int
?len);
static
?
void
?_adjust_heap(
int
?
*
array,
int
?idx,
int
?len);
int
?heap_sort(
int
?
*
array,
int
?begin,
int
?end)
{
????
if
(array
==
NULL
||
begin
>
end)?
return
?
0
;
????
//
自此以后，index從1開始。
????array
--
;
????
int
?len?
=
?end
-
begin
+
1
;
????_build_heap(array,len);
????
int
?tmp;
????
int
?i;
????
for
(i
=
1
;i
<
len;
++
i){
????????tmp?
=
?array[len
-
i
+
1
];
????????array[len
-
i
+
1
]?
=
?array[
1
];
????????array[
1
]?
=
?tmp;
????????_adjust_heap(array,
1
,len
-
i);
????}
}
//
input:?任意數組?output:大頂堆
static
?
void
?_build_heap(
int
?
*
array,
int
?len)
{
???
int
?i;
???
for
(i
=
len
/
2
;i
>=
1
;
--
i){
????????_adjust_heap(array,i,len);
???}
}
//
使重新使array滿足堆特性
static
?
void
?_adjust_heap(
int
?
*
array,
int
?idx,
int
?len)
{
????
int
?left;
????
int
?right;
????
int
?larger?
=
?idx;
????
int
?tmp?
=
?array[idx];
????left?
=
?(idx
<<
1
);
????right?
=
?left
+
1
;
????
while
(?left
<=
?len){
????????
if
(right
<=
len
&&
array[right]
>
array[left]){
????????????larger?
=
?right;?
????????}
else
{
????????????larger?
=
?left;
????????}
????????
if
(?array[larger]
>
tmp?){
????????????array[idx]?
=
?array[larger];
????????????idx?
=
?larger;
????????????left?
=
?(idx
<<
1
);
????????????right?
=
?left
+
1
;
????????}
else
{
????????????
break
;
????????}
????}
????array[idx]?
=
?tmp;
}