1、堆结构
堆这种数据结构首先是一种特殊的完全二叉树，且满足子节点值大于父节点点值的大或小。
2、首先取未排序数组4,3,7,1,8,5。下面我们演示一下该算法的实现步骤。
3、根据数组元素的位置，首先构建一个完全二叉树，填满一层之后再填满下一层。
4、调整完全二叉树中元素的次序，保证每一个节点元素要比他的子节点元素要大，构成一个大顶堆。
5、这个时候该纾解点的根节点元素是所有元素中最大的元素。只要按照把根节点一次提取出来即可。
6、提供代码：
#include <iostream>
using namespace std;
void heapify(int arr[],int n,int i)
{
int smallest=i;
int l=2*i+1;
int r=2*i+2;
if (l<n&&arr[l]<arr[smallest])
smallest=l;
if (r<n&&arr[r]<arr[smallest])
smallest=r;
if (smallest!=i)
{
swap(arr[smallest],arr[i]);
i=smallest;
heapify(arr,n,i);
}
}
void heapsort(int arr[],int n)
{
for (int i=n/2-1;i>=0;i--)
heapify(arr,n,i);
for (int i=n-1;i>=0;i--)
{
swap(arr[0],arr[i]);
heapify(arr,i,0);
}
}
void printarray(int arr[],int n)
{
for(int i=n-1;i>=0;i--)
cout<<arr[i]<<" ";
cout<<endl;
}
int main()
{
int arr[]={3,8,2,9,12,5};
int n=sizeof(arr)/sizeof(int);
cout<<"origin array:";
printarray(arr,n);
heapsort(arr,n);
cout <<"sorted array:";
printarray(arr,n);
return 0;
}
