堆排序数据结构 堆排序（初阶数据结构）

  一、堆的基本概念

  在空间结构上时一维数组，在逻辑结构上满足“父节点的值均不小于（不大于）子节点”堆排序数据结构，逻辑结构上 堆是一个完全二叉树。由父节点与子节点的关系堆排序数据结构，又可以分为大堆和小堆，其中根节点为堆顶。堆顶是最大值或者最小值；

  二、堆的实现

  堆实质上是一个数组 所以类顺序表的设计

   #include

    #include
    #include
    #include
    #include
    typedef int HPDataType;
    typedef struct Heap
    {
        HPDataType* _a;
        int _size;
        int _capacity;
    }Heap;
    //堆的初始化：
    //初始化堆
    void Heapinit(Heap*hp)
    {
        assert(hp);
        hp->_a = NULL;
        hp->_capacity = hp->_size = 0;

  以下为了方便 以大堆为例（小堆变换调整符号即可）

  接口

   //向上调整

    void AdjustUp(HPDataType*a, size_t child);
    //向下调整
    void AdjustDown(HPDataType*a, size_t size);
    // 堆的销毁
    void HeapDestory(Heap* hp);
    // 堆的插入
    void HeapPush(Heap* hp, HPDataType x);
    // 堆的删除
    void HeapPop(Heap* hp);
    // 取堆顶的数据
    HPDataType HeapTop(Heap* hp);
    // 堆的数据个数
    int HeapSize(Heap* hp);
    // 堆的判空

  1.堆数据的插入

   void HeapPush(Heap* hp, HPDataType x)

    {
        assert(hp);
        if (hp->_capacity _size)
        {
            //开辟一块空间 如果是0；就开辟四个整形的大小，一次扩容两个整形的大小
            int newcapacity = hp->_capacity== 0 ? 4 : hp->_capacity * 2;
            HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
            if (tmp == NULL)
            {
                perror("realloc fail");
                exit(-1);
            }
            hp->_a = tmp;
            hp->_capacity = newcapacity;
        }
        hp->_a[hp->_size] = x;
        AdjustUp(hp->_a, hp->_size);
        hp->_size++;

  约定成俗 有两个公式：

   //父节点

    parent=(child-1)/2;
    //子节点
    leftchild=parent*2+1;//左孩子

  向上调整法：

   //向上调整（即建立大堆时，将大的数向上调整）

    //push时复用
    void AdjustUp(HPDataType*a , size_t child)
    {
        assert(a);
        while (child != 0)
        {
            size_t parent = (child - 1) / 2;
            if (a[child] > a[parent])
            {
    //如果子节点大于父节点则需要调整
    //将子节点向上调整
                Swap(&a[child], &a[parent]);
            }
            else
            {
                break;
            }
    //更新下标
            child = parent;
        }

  向下调整法：

   void AdjustDown(HPDataType*a, size_t size)

    {
        assert(a);
        size_t parent = 0;
        size_t child = parent * 2 + 1;
        while (child < size)
        {
            if (child + 1 < size && a[child] < a[child + 1])
            {//确保child是左右中大的那一个
                child++;
            }
            if (a[parent] < a[child])
            {
                Swap(&a[parent], &a[child]);
            }
            else
            {
                break;
            }
    //更新下标
    //再与后面的子树比较
            parent = child;
            child = parent * 2 + 1;
        }

  函数的实现

  当堆中没有存放数据时，一个空堆插入，不同于顺序表的尾插堆排序数据结构 堆排序（初阶数据结构），堆结构需要在插入数据时保持结构成立（父节点大于/小于子节点）

   void HeapPush(Heap* hp, HPDataType x)

    {
        assert(hp);
        if (hp->_capacity _size)
        {
            //开辟一块空间 如果是0；就开辟四个整形的大小，一次扩容两个整型的大小
            int newcapacity = hp->_capacity== 0 ? 4 : hp->_capacity * 2;
            HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
            if (tmp == NULL)
            {
                perror("realloc fail");
                exit(-1);
            }
            hp->_a = tmp;
            hp->_capacity = newcapacity;
        }
        hp->_a[hp->_size] = x;
    //即插入即排序
        AdjustUp(hp->_a, hp->_size);
        hp->_size++;

  函数的删除

  将根与最后一个叶子交换 size--删除 再将新根向下重新排序

   void HeapPop(Heap* hp)

    {
        assert(hp);
        assert(hp->_size > 0);
        Swap(&hp->_a[0], &hp->_a[hp->_size-1]);
        hp->_size--;
        AdjustDown(hp->_a, hp->_size);

   //取顶

    HPDataType HeapTop(Heap* hp)
    {
        assert(hp);
        assert(hp->_size > 0);
        return hp->_a[0];
    }
    //大小
    int HeapSize(Heap* hp)
    {
        assert(hp);
        return hp->_size;
    }

  调试结果

  一个堆就实现啦~~有错误欢迎指正

  文章来源:https://blog.csdn.net/weixin_69479577/article/details/128401017