3.1 二叉树的顺序结构

普通的二叉树是不适合用 数组来存储的，因为可能会存在大量的空间浪费。而 完全二叉树更适合使用顺序结
构存储。现实中我们通常把 堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统
虚拟进程地址空间中的堆是两回事，一个是 数据结构，一个是 操作系统中管理内存的一块区域分段。

3.2 堆的概念及结构

如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储
在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆(或大堆)。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树。

注意：堆只规定了父节点比孩子节点的关系，并没有规定左右孩子之间的关系

3.3 堆的实现

3.2.1 堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整
成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

                                int arr[] = { 27,15,19,18,28,34,65,49,25,37 };//物理结构是数组，逻辑结构是完全二叉树

//向下调整算法
void AdjustDown(int* a, int n, int parent)
{
    int midchild = parent * 2 + 1;
    while (midchild < n)
    {
        //建小堆找小的那个孩子，建大堆找的大的孩子
        if (midchild + 1 < n && a[midchild] > a[midchild + 1])//建小堆
        {
            midchild++;
        }
        if (a[parent] > a[midchild])
        {
            Swap(&a[parent], &a[midchild]);
            parent = midchild;
            midchild = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

3.2.2堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算
法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的
子树开始调整，一直调整到根节点的树，就可以调整成堆。

                                      int arr[] = { 1,5,3,8,7,6 };

堆的创建可以使用向下调整算法，也可以使用向上调整算法，这里演示一下向上调整算法的实现过程

#include<stdio.h>
//交换元素
void Swap(int* e1, int* e2)
{
    int tem = *e1;
    *e1 = *e2;
    *e2 = tem;
}

//向下调整算法
void AdjustDown(int* a, int n, int parent)
{
    int midchild = parent * 2 + 1;
    while (midchild < n)
    {
        //建小堆找小的那个孩子，建大堆找的大的孩子
        if (midchild + 1 < n && a[midchild] < a[midchild + 1])
        {
            midchild++;
        }
        if (a[parent] < a[midchild])
        {
            Swap(&a[parent], &a[midchild]);//交换
            parent = midchild;
            midchild = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
//向上调整算法
void AdjustUp(int* a, int child)
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[parent] < a[child])
        {
            Swap(&a[parent], &a[child]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

int main()
{
    int arr[] = { 1,5,3,8,7,6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    //方法一：向下调整算法
    //从最后一个非叶子节点开始调整，最后一个非叶子节点就是最后一个节点的父亲，
    //parent=(child-1)/2,  这里的最后一个元素为n-1，所以child=n-1，故parent=(n-1-1)/2
    for (int i = (n - 1-1)/2; i >= 0; --i)//建大堆
    {
        AdjustDown(arr,n, i);
    }


//方法二：向上调整算法
//注意，向上调整算法是从数值一个元素开始
//    for (int i = 0; i < n;  ++i)//建大堆
//    {
//        AdjustUp(arr, i);
//    }


    for (int i = 0; i <n; ++i)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

既然向上调整算法和向下调整算法都可以建堆，那我们应该使用那一种呢？

建议使用向下调整算法，因为它的时间复杂度为O(N)，向上调整算法的时间复杂度为
N*log(N)，（以2为底的对数）

3.2.3 建堆时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的
就是近似值，多几个节点不影响最终结果)：

3.2.4 堆的插入

• 假设：向堆中插入一个10

操作过程：先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆

3.2.5 堆的删除

• **删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调

整算法。**

3.2.6 堆的代码实现

//头文件Heap.h
#pragma once

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
    HPDataType* a;
    int size;//有效个数
    int capacity;//堆的容量
}Heap;

//堆的初始化
void HeapInit(Heap* php);
//堆的销毁
void HeapDestroy(Heap* php);
//堆的打印
void HeapPrint(Heap* php);
//堆的插入
void HeapPush(Heap* php, HPDataType x);
//堆的删除
void HeapPop(Heap* php);
//返回堆顶元素
HPDataType HeapTop(Heap* php);
//返回堆的元素个数
int HeapSize(Heap* php);
//判断堆是否为空
bool HeapEmpty(Heap* php);

//函数实现文件Heap.c
#include"Heap.h"

void HeapInit(Heap* php)
{
    assert(php);
    php->a = NULL;
    php->capacity = php->size = 0;
}

void HeapDestroy(Heap* php)
{
    assert(php);
    free(php->a);
    php->a = NULL;
    php->capacity = php->size = 0;
}

void Swap(HPDataType* x1, HPDataType* x2)
{
    HPDataType tem = *x1;
    *x1 = *x2;
    *x2 = tem;
}

//向上调整算法
void AdjustUp(HPDataType* a, int child)
{
    assert(a);
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent= (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

void HeapPush(Heap* php, HPDataType x)
{
    assert(php);
    if (php->capacity == php->size)
    {
        int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tem = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
        if(tem==NULL)
        {
            perror("realloc fail");
            exit(-1);
        }
        php->a = tem;
        php->capacity = newcapacity;
    }
    php->a[php->size] = x;
    php->size++;

    AdjustUp(php->a,php->size-1);
}

//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)
{
    int midchild = parent * 2 + 1;
    while (midchild < n)
    {    
        // 找出小的那个孩子
        if (midchild +1< n && a[midchild] > a[midchild + 1])
        {
            midchild++;
        }
        if (a[parent] > a[midchild])
        {
            Swap(&a[parent], &a[midchild]);
            parent = midchild;
            midchild = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void HeapPop(Heap* php)
{
    assert(php);
    assert(!HeapEmpty(php));
    Swap(&php->a[0], &php->a[php->size - 1]);
    php->size--;

    AdjustDown(php->a, php->size, 0);
}

HPDataType HeapTop(Heap* php)
{
    assert(php);
    assert(!HeapEmpty(php));
    return php->a[0];
}

int HeapSize(Heap* php)
{
    assert(php);
    return php->size;
}

bool HeapEmpty(Heap* php)
{
    assert(php);
    return php->size == 0;
}

void HeapPrint(Heap* php)
{
    assert(php);
    for (int i = 0; i < php->size; i++)
    {
        printf("%d ", php->a[i]);
    }
    printf("\n");
}