思路
1.建堆（大根堆为例） （1）从倒数第一个非叶子节点开始，做下沉操作，直到根节点。 （2）下沉操作，对父节点和其儿子节点做比较，若父节点最大，则结束，否则就下沉，然后对发生变化的儿子节点做同样的下沉操作，直到叶子节点。 2.堆排序 （1）将根节点与最后一个叶子节点互换位置； （2）对根节点做下沉操作。
C++实现
#include <iostream>
#include <vector>
#include <functional>
using namespace std
;
template<class T>
void shiftDown(vector
<T
>& a
, int i
, int len
, function
<bool(const T
&, const T
&)>cmp
) {
int l
= 2 * i
+ 1;
int r
= l
+ 1;
int m
= i
;
while(l
< len
) {
if(!cmp(a
[l
], a
[i
]) && (r
>= len
|| !cmp(a
[l
], a
[r
])) ) {
m
= l
;
}
else if(r
< len
&& !cmp(a
[r
], a
[i
]) && !cmp(a
[r
], a
[l
])) {
m
= r
;
}
if(m
!= i
) {
swap(a
[m
], a
[i
]);
l
= 2 * m
+ 1;
r
= l
+ 1;
i
= m
;
}
else {
break;
}
}
}
template<class T>
void createHeap(vector
<T
>& a
, int len
, function
<bool(const T
&, const T
&)>cmp
) {
for(int i
= len
/ 2 - 1; i
>= 0; --i
) {
shiftDown(a
, i
, len
, cmp
);
}
}
template<class T>
void popHeap(vector
<T
>& a
, int len
, function
<bool(const T
&, const T
&)>cmp
) {
swap(a
[0], a
[len
- 1]);
shiftDown(a
, 0, len
- 1, cmp
);
}
template<class T>
void heapSort(vector
<T
>& a
, int len
, function
<bool(const T
&, const T
&)>cmp
) {
createHeap(a
, len
, cmp
);
for(int i
= len
; i
>= 2; --i
) {
popHeap(a
, i
, cmp
);
}
}
int main() {
vector
<int> a
{0, 10, 1, 2, 0, 11, -3};
heapSort
<int>(a
, a
.size(), [](const int& l
, const int& r
) {
return l
< r
;
});
for(auto i
: a
) {
cout
<< i
<< ' ';
return 0;
}
运行结果：
-3 0 0 1 2 10 11
总结
自底向上的建堆复杂度为O(n)堆排序的复杂度为O(nlogn)堆是原地排序，但不稳定
