【算法】堆排序算法Heap Sort_应从哪个节点开始出发做heapify

视频学习：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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

这个代码之后建成的堆

代码二：建堆

从倒数第二层开始做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);
	} 
}
1
2
3
4
5
6
7
8
9
10

建堆之后做堆排序

此时已经可以保证每个父节点都大于子节点

完整版代码

#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;
}
   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68