堆排序

堆排序

视频教程

![1.png)

#include<bits/stdc++.h>
using namespace std;
void swap(int arr[],int i,int j){
    int temp = arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
}
void heapify(int tree[],int n,int i){  //交换父节点和子节点的函数,一个交换操作
    if(i>=n){                          //递归出口
        return ; 
    }
    int c1 = i*2+1;                    //第一个子节点
    int c2 = i*2+2;                    //第二个子节点
    int maxx = i;
    if(c1<n && tree[c1]>tree[maxx]){
        maxx = c1;
    } 
    if(c2<n && tree[c2]>tree[maxx]){
        maxx = c2;
    }
    if(maxx!=i){
        swap(tree,maxx,i);
        heapify(tree,n,maxx);
    }
}
//从最后一个节点开始建树
void buildtree(int tree[],int n){   //创建一个堆
    int last_node = n-1;            //最后一个节点
    int parent = (last_node-1)/2;   //知道当然节点求它的父节点
    for(int i=parent;i>=0;i--){
        heapify(tree,n,i);
    }
}
//排序,把最后一个节点和第一个节点交换,第一个节点肯定是最大的(在建树过程中就已经决定了),一直把最后一个节点去除
void heapify_sort(int tree[],int n){
    buildtree(tree,n);
    for (int i = n-1;i>=0;i--){
        swap(tree,i,0);
        heapify(tree,i,0);
    }
}

int main(){
    int a[10]={1,5,9,1,2,3,6,4,54,8};
    int n = 10;
    heapify_sort(a,n);
    for(auto v:a){
        cout<<v<<endl;
    }
    return 0;
}