堆的建立
分数 20
作者 张志梅
单位 青岛大学
所谓“堆的建立”，是指将已经存在的N个元素调整成最大堆或最小堆。
输入格式:
第一行是一个整数N，表示元素的个数，N<=10000。第二行N个元素的值。
输出格式:
输出2行，第一行是输入序列调整为最大堆后的元素序列，元素之间用空格分开。第二行是输入序列调整为最小堆后的元素序列，元素之间用空格分开。
输入样例:
在这里给出一组输入。例如：
8
7 5 8 4 2 3 6 1
输出样例:
在这里给出相应的输出。例如：
8 5 7 4 2 3 6 1
1 2 3 4 7 8 6 5
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
#include <stdio.h>
int max(int a,int b)
{
return a > b ? a:b;
}
int min(int a,int b)
{
return a > b ? b:a;
}
void swap(int *a,int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void printfArr(int arr[],int n)
{
for (int i =1; i <= n; i++)
{
printf("%d",arr[i]);
if (i != n)
{
printf(" ");
}
}
printf("\n");
}
// void heap(int arr[],int *func,int n)
// {
// }
int main()
{
int n;
int flag;
scanf("%d",&n);
int *arr,arr1[n + 1],arr2[n + 1];
for (int i =1; i <= n; i++)
{
scanf("%d",&arr1[i]);
arr2[i] = arr1[i];
}
if (n == 1)
{
printf("%d\n%d",arr1[1],arr1[1]);//数组下标从一开始
return 1;
}
int (*func)(int ,int ); //函数指针
//建大堆
arr = arr1;
func = max; //函数指针指向max函数
for (int j = n; j >= 1; j -= 2)
{
int flag = 0;
for (int i = n; i > 1; i -= 2)//从下往上更一次
{
if (flag == 0 && n % 2 == 0) //偶数//初始状态最后一个节点为左孩子，稍作处理让最后一个孩子为右孩子方便操作
{
flag = 1; //只进入一次该条件
if (func == min && arr[n] < arr[n/2])
{
swap(&arr[n],&arr[n/2]);
}
else if (func == max && arr[n] > arr[n/2])
{
swap(&arr[n],&arr[n/2]);
}
i--;
if (i == 1) break; //如果n为2交换一次直接退出
}
int temp;
temp = func(func(arr[i],arr[i-1]),arr[(i-1)/2]);
if (arr[i-1]==temp) //父节点和左右两孩子中左孩子最大将左孩子和父节点交换
{
swap(&arr[i-1],&arr[(i-1)/2]);
}
else if (arr[i] == temp)//父节点和左右两孩子中右孩子最大将右孩子和父节点交换
{
swap(&arr[i],&arr[(i-1)/2]);
}
}
}
printfArr(arr,n);
// 建小堆
arr = arr2; //整型指针指向arr2数组
func = min; //函数指针指向min函数
for (int j = n; j >= 1; j -= 2)
{
int flag = 0;
for (int i = n; i > 1; i -= 2)//从下往上更一次
{
if (flag == 0 && n % 2 == 0) //偶数//初始状态最后一个节点为左孩子，稍作处理让最后一个孩子为右孩子方便操作
{
flag = 1; //只进入一次该条件
if (func == min && arr[n] < arr[n/2])//建最小堆时，如果上面的值要大把两个值进行交换让上层的值小
{
swap(&arr[n],&arr[n/2]);
}
else if (func == max && arr[n] > arr[n/2])建最大堆时，如果上面的值要小把两个值进行交换让上层的值大
{
swap(&arr[n],&arr[n/2]);
}
i--;
if (i == 1) break; //如果n为2交换一次直接退出
}
int temp;
temp = func(func(arr[i],arr[i-1]),arr[(i-1)/2]);
if (arr[i-1]==temp) //父节点和左右两孩子中左孩子最大将左孩子和父节点交换
{
swap(&arr[i-1],&arr[(i-1)/2]);
}
else if (arr[i] == temp)//父节点和左右两孩子中右孩子最大将右孩子和父节点交换
{
swap(&arr[i],&arr[(i-1)/2]);
}
}
}
printfArr(arr,n);
}
堆百度百科 https://baike.baidu.com/item/%E5%A0%86/20606834
由于堆是一个完全二叉树我们可以用数组很好的模拟堆的结构，一开始我理解的是只要符合
- 堆中某个结点的值总是不大于或不小于其父结点的值；
- 堆总是一棵完全二叉树。
就是一个堆，然后我从顶部开始建堆，但是后来发现一提交题目神奇的一幕出现了。
全错。。。然后经过与同学讨论和查阅博客发现，人家堆的插入是从底部开始建立的为了尽可能少的改变树的节点位置。看到题目要求：第二行是输入序列调整为最小堆后的元素序列并没有什么想法。当我用最大堆去建最小堆的时候发现会和输入序列建最小堆结果不一样，但是输出序列依旧符合堆结构，当时甚至考虑是不是题目的样例固定，没有考虑所有的情况肯定是题目的问题。在某一刻突然想到是不是因为从根节点建左边的节点在某些情况会跑到右边去了才错了，然后去重构了自己的代码换成从根节点开始建堆，这样可以让左边的值永远在左边最多就跑到根节点。最后：
终于通过了，应该考虑每个分叉都当作一个堆去考虑，不只是整颗树建成一个堆才行，左边的值不能随便跑到右边。代码行数比较多本来想将最大堆和最小堆做成一个函数，但是实现语法超出了我的学习范围，最后提交还是直接将建大堆复制了一份把判断最大改成了最小。
