#include <iostream>
// 堆调整（非递归版）
void max_heapify_no_recur(int a[], int len, int i)
{
int l = 0;
int r = 0;
int m = 0;
while (true) {
l = i * 2 + 1; //左节点
r = i * 2 + 2; //右节点
m = i;
// 找出最大值节点
if (l < len && a[l] > a[m]) {
m = l;
}
if (r < len && a[r] > a[m]) {
m = r;
}
if (m != i) {
// 把当前节点设为最大，继续调整子节点
std::swap(a[i], a[m]);
i = m;
}
else {
break;
}
}
}
// 堆调整（递归版）
void max_heapify(int a[], int len, int i)
{
int l = i * 2 + 1; //左节点
int r = i * 2 + 2; //右节点
int m = i;
// 找出最大值节点
if (l < len && a[l] > a[m]) {
m = l;
}
if (r < len && a[r] > a[m]) {
m = r;
}
if (m != i) {
// 把当前节点设为最大，递归调整子节点
std::swap(a[i], a[m]);
max_heapify(a, len, m);
}
}
// 建堆
void build_max_heap(int a[], int len)
{
for (int i = len/2 - 1; i >= 0; i--) {
// max_heapify(a, len, i);
max_heapify_no_recur(a, len, i);
}
}
// 堆排序
void heap_sort(int a[], int len)
{
build_max_heap(a, len);
for (int i = len - 1; i > 0; i--) {
std::swap(a[i], a[0]);
// max_heapify(a, i, 0);
max_heapify_no_recur(a, i, 0);
}
}
int main(int argc, const char * argv[])
{
int a[] = {1, 1, 6, 6, 8, 3, 5, 100, 300, 200, 99, 99};
heap_sort(a, sizeof(a)/sizeof(a[0]));
for (int i : a) {
std::cout << i << ' ';
}
std::cout << std::endl;
return 0;
}
堆排序-C++代码
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 选择排序 对于任何输入，时间为O(n*n)； 冒泡排序 最优（对于升序的数组，因为加入了一个跳出判断）：O(n)，...
- 上一篇C++基础入门之模板堆排序(上):模板上的list的创造与操作 其实接下来就很简单了，只要把大众版的堆排序翻...
- 堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出(最大堆调整的递归运算)，这...
- 堆排序 (二叉)堆是一个数组，它可以被看成一个近似的完全二叉树。树上的每一个结点对应数组中的一个元素。除了最底层外...
