首页 / 算法 / 堆排序(最小堆)C++
堆排序(最小堆)C++
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了堆排序(最小堆)C++,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1631字,纯文字阅读大概需要3分钟。
内容图文
堆分为大根堆(最大堆)和小根堆(最小堆),堆排序就是二叉堆的升级版,实际上是一棵完全二叉树
不同的是这棵二叉树里每个节点保证父节点都小于孩子节点
最后进行堆排序,将堆顶最小的节点(第一个)与最后一个节点(最大的节点)进行交换,对剩下的进行调节,令其满足最小堆
#include <iostream>
#include <cstdlib>
using namespace std;
void MaxHeapIfy(int A[], int length, int i) //维护
{
int left = i * 2; //节点i的左孩子
int right = i * 2 + 1; //节点i的右孩子节点
int largest = i; //默认父节点
if (left <= length && A[largest] < A[left]) //左孩子比父节点大
{
largest = left;
}
if (right <= length && A[largest] < A[right]) //右孩子最大
{
largest = right;
}
if (i != largest) //最大值不是父节点
{
int temp = A[largest]; //exchange
A[largest] = A[i];
A[i] = temp;
MaxHeapIfy(A, length, largest); //继续维护
}
}
void BuildMaxHeap(int A[], int length) //建堆
{
for (int i = length / 2; i >= 1; i--)
{
MaxHeapIfy(A, length, i);
}
}
void HeapSort(int A[], int length) //堆排
{
int temp;
BuildMaxHeap(A, length); //建堆
/*
cout<<"建堆情况:"; //
for(int i = 1; i <= length; i++)
cout<<A[i]<<" ";
cout<<endl;
*/
for(int i = length; i >= 2;)
{
temp = A[i]; //交换堆的第一个元素和堆的最后一个元素
A[i] = A[1];
A[1] = temp;
i--; //堆的大小减一
MaxHeapIfy(A, i, 1); //调堆
}
}
int main()
{
int A[] = {0, 4, 1, 23, 3, 2, 16, 9, 10, 14, 8, 7}; //0只做填充,填充A[0]
/*int* A = new int[1001];
A[0] = 0;
for(int i = 1; i <= 1000; i++)
A[i] = rand()%10000 + 1;*/
int length = sizeof(A) / sizeof(int); //
//int length = 1001;
HeapSort(A, length - 1);
for(int i = 1; i < length; i++) //cout
cout<<A[i]<<" ";
cout<<endl;
return 0;
}
原文为https://blog.csdn.net/xjm199/article/details/18011321
内容总结
以上是互联网集市为您收集整理的堆排序(最小堆)C++全部内容,希望文章能够帮你解决堆排序(最小堆)C++所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。