【算法】堆排序算法Heap Sort

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

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

## 堆排序基础 ##

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

### 完全二叉树 ###

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

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

这样就不是完全二叉树（这里构造完全二叉树要从最左边开始添加）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 1]  
这样就是个完全二叉树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 2]  
大顶堆完全二叉树：父节点一定要大宇子节点，如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 3]

## 建堆 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 4]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 5]

### 代码一：建堆 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 6]

*这个代码之后建成的堆*  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 7]

### 代码二：建堆 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 8]  
*从倒数第二层开始做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);
    	} 
    }

## 建堆之后做堆排序 ##

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

### 完整版代码 ###

#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;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/2c1dc904c18341d3a238eff9314a741a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221024/c38ca41558d041b8b65351cbc77a6866.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221024/9679ad81c5584180aceaa1e304826ed7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221024/f77b6e0942be4641b8d5ef196a3de405.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221024/38ea8cdc30694077bddde44c29ff0242.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221024/0e0dab325c804e5e980eb1abb409a8e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221024/a4f08f233201404894ea68cd9ee25121.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221024/3c4f29ca91eb48ef8d623e15226ad5c6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221024/0debbab1b17943d0bb9b4d00d1a5b5d2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221024/e4d2561f2ca444f8ac9adc4e8076d27f.png