【算法】堆排序算法Heap Sort-蒲公英云

【算法】堆排序算法Heap Sort

叁歲伎倆 2022-10-31 00:50 233阅读 0赞

视频学习：https://www.bilibili.com/video/BV1Eb41147dK

堆排序基础

（1）满足完全二叉树
（2）父节点的值大于子节点的值（视频讲的是大顶堆）

完全二叉树

在这里插入图片描述
这七个都是完全二叉树

完全二叉树：一个父节点只能有两个子节点，并且必须从上到下，从左到右这样生成节点。

这样就不是完全二叉树（这里构造完全二叉树要从最左边开始添加）
在这里插入图片描述
这样就是个完全二叉树

大顶堆完全二叉树：父节点一定要大宇子节点，如下

建堆

在这里插入图片描述

代码一：建堆

在这里插入图片描述

#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)//建堆 
{
    //n是有多少个节点，i是对哪个节点做heapify操作 
    if(i>=n)
    {
        return 0;
    } 
    int c1=2*i+1;
    int c2=2*i+2;
    int max=i;
    //在三个值中要找出最大值 
    if(c1<n&&tree[c1]>tree[max]) 
    {
        max=c1;
    }
    //c1小于n是为了防止越界 
    if(c2<n&&tree[c2]>tree[max])
    {
        max=c2;
    } 
    if(max!=i)
    {
        swap(tree,max,i);//如果max不等于i，那么交换max和i，此时tree[max] 
        heapify(tree,n,max);//递归，对下一个子节点（即下一个堆的父节点）继续做heapify 
    }
}
int main()
{
    int tree[]={
    4,10,3,5,1,2}
    int n=6;
    heapify(tree,n,0);
    int i;
    for(i=0;i<n;i++)
    {
        cout<<tree[i]<<endl;
    } 
    return 0;
}

这个代码之后建成的堆
在这里插入图片描述

代码二：建堆

在这里插入图片描述
从倒数第二层开始做heapify，一个个节点往上排序

void build_heap(int tree[],)
{
    int last_node=n-1;//要开始heapify的最后一个节点 
    int parent=(last_node-1)/2;
    int i;
    for(i=parent;i>=0;i--)
    {
        heapify(tree,n,i);
    } 
}

建堆之后做堆排序

此时已经可以保证每个父节点都大于子节点
在这里插入图片描述

完整版代码

#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 ;
    } 
    //n是有多少个节点，i是对哪个节点做heapify操作 
    int c1=2*i+1;
    int c2=2*i+2;
    int max=i;
    //在三个值中要找出最大值 
    if(c1<n&&tree[c1]>tree[max]) 
    {
        max=c1;
    }
    //c1小于n是为了防止越界 
    if(c2<n&&tree[c2]>tree[max])
    {
        max=c2;
    } 
    if(max!=i)
    {
        swap(tree,max,i);//如果max不等于i，那么交换max和i，此时tree[max] 
        heapify(tree,n,max);//递归，对下一个子节点（即下一个堆的父节点）继续做heapify 
    }
}
void build_heap(int tree[],int n)
{
    int last_node=n-1;//要开始heapify的最后一个节点 
    int parent=(last_node-1)/2;
    int i;
    for(i=parent;i>=0;i--)
    {
        heapify(tree,n,i);
    } 
}
void heap_sort(int tree[],int n)
{
    build_heap(tree,n);
    int i;
    for(i=n-1;i>=0;i--)
    {
        swap(tree,i,0);//交换头尾两个数 
        heapify(tree,i,0);//i代表剩下的节点数量（i不断减少代表着堆的节点不断被砍断） 
    }
}
int main()
{
    int tree[]={
    4,10,3,5,1,2};
    int n=6;
    heap_sort(tree,n);
    int i;
    for(i=0;i<n;i++)
    {
        cout<<tree[i]<<endl;
    } 
    return 0;
}