扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
利用数组模拟一棵完全二叉树，根据数组下标可以快速确定一个结点的左右孩子和父母。
例如根结点下标为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元起，快前往官网查看详情吧
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网