将二叉树调整成大根堆,之后排序

  • Post author:
  • Post category:其他


#include<stdio.h>
#include<stdlib.h>
//调整成大根堆函数
void Make_A_Heap(int a[], int n)
{
    int t, end, pa, tag;
    //初始化数据域
    end = n;
    tag = 1;
    while (tag)
    {
        pa = end / 2;
        tag = 0;
        while (pa > 0)
        {
            if (a[pa] < a[2 * pa])
            {
                t = a[pa];
                a[pa] = a[2 * pa];
                a[2 * pa] = t;
                tag = 1;
            }
            if ((2 * pa + 1<= end)&&a[2 * pa + 1] > a[pa])
            {
                t = a[2 * pa + 1];
                a[2 * pa + 1] = a[pa];
                a[pa] = t;
                tag = 1;
            }
            pa--;
        }
    }
}
//排序函数
void Sort_Heap(int a[], int n)
{
    int t, end=n;
    while (end-1)
    {
        Make_A_Heap(a, end);
        //交换a[1]和a[end],数组长度长度减1
        t = a[1];
        a[1] = a[end];
        a[end] = t;
        end--;
    }
}
int main(void)
{
    //创建一个二叉树
    int a[9] = { 0,3,2,5,8,4,7,6,9 };
    //Make_A_Heap(a, 8);
    Sort_Heap(a, 8);
    for (int i = 1; i < 9; i++)
    {
        printf("%5d",a[i]);
    }
    system("pause");
    return 0;
}



版权声明:本文为xiao_ren_wu_原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。