堆排序-从小到大-创新互联
利用数组模拟一棵完全二叉树,根据数组下标可以快速确定一个结点的左右孩子和父母。
例如根结点下标为5,下标10为其左孩子,11为右孩子,2为双亲。
非常适合处理的问题:在只能存储一定数据时,而总元素个数较大,只需取前k个小的数
时间复杂度O(nlogn)
#include#include#include#include
#include#includeusing namespace std;
#define N 100005
#define pi 3.14159
typedef long long ll;
int a[N];//存储数据
void adjustHeap(int i, int len)//调整堆//down
{a[0] = a[i];//a[0]保存根的值
for (int j = 2 * i; j<= len; j*=2)//找更大的孩子
{if (j< len && a[j]< a[j + 1]) j++;//a[j]为左孩子,a[j+1]为右孩子
if (a[0] >= a[j]) break;//根已经比孩子大,符合大顶堆
else
{ a[i] = a[j];//将大的孩子的值给根
i = j;//选定的孩子作为新根
}
}
a[i] = a[0];//归还
}
void creatHeap(int len)//建堆
{for (int i = len / 2; i >0; i--)
{adjustHeap(i, len);
}
}
void heapSort(int len)
{creatHeap(len);
for (int i = len; i >1; i--)
{swap(a[1], a[i]);//将堆顶的大元素放到最后面
adjustHeap(1, i - 1);
}
}
int main()
{int n;
scanf("%d", &n);
for (int i = 1; i<= n; i++)
{scanf("%d", &a[i]);
}
heapSort(n);
for (int i = 1; i<= n; i++)
{printf("%d ", a[i]);
}
return 0;
}
实现从小到大排序则建立大顶堆,实现从大到小建立小顶堆
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
当前题目:堆排序-从小到大-创新互联
文章链接:http://myzitong.com/article/jdgdd.html