怎样使用c++语言实现简单的堆排序

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;

}