#include<stdio.h>
#include<stdlib.h>
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) //i表示的是要对哪个节点做操作，n表示由多少个节点
{
if (i >= n) //出口
return;
int c1 = 2 * i + 1;
int c2 = 2 * i + 2;
int max = i;//假设一个最大的节点
if (c1<n && tree[c1]>tree[max])//防止越界
{
max = c1;
}
if (c2<n && tree[c2]>tree[max])//防止越界
{
max = c2;
}
if (max != i)//这里就是防止一个数的下标是i的数本身就是最大的，防止自己交换自己
{
swap(tree, max, i);
heapify(tree, n, max);
}
}
void build_heap(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 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本来是n的，但是n一直再变化,所以写i就可以了
}
}
总结:因为堆里面第一个是最小的或者是最小的，所以我们可以挨个取出来，然后再重新排序，最后排序成功
觉得可以的兄弟关注一波，我持续更新，不懂的问我