关于数据结构:数据结构与算法-C-最大小堆的插入与删除

用数组实现最大/小堆，有两种形式，一种是Array[0]不存理论值，另一种是Array[0]存理论值。
第一种的话，数组长度比堆结点数多1，因为[0]是没有存任何结点的,对于i的左右子结点为2i和2i + 1，父节点为(i - 1)/2;
第二种的话，数组长度等于堆结点数，因为[0]是根结点的,对于i的左右子结点为2i + 1和2i + 2，父节点为i/2。
这里以最大堆为例；

C语言实现第一种：

#include <stdio.h>#include <stdlib.h>typedef struct MaxHeap {    int *data; //数据域    int size; //长度    int max;//最大长度} MaxHeap;//插入新结点void insert(struct MaxHeap *p, int item){    if (p->size == p->max)    {        printf(":\n");        return;    }    int i = ++p->size;//先加1再复制给int，这样第一个插入的数组下标就是1    for (; p->data[i/2] < item; i/=2)//上浮    {        if (i <= 1)        {            break;        }        p->data[i] = p->data[i/2];    }    p->data[i] = item;}//删除根节点，void delete(struct MaxHeap *p){    p->data[1] = p->data[p->size--];    int i = 1;    int tmp;    while(2*i <= p->size){        //如果有右节点        if (2*i + 1 <= p->size)        {            if (p->data[2*i + 1] > p->data[i] || p->data[2*i] > p->data[i])            {                if (p->data[2*i + 1] > p->data[2*i])                {                    tmp              = p->data[i];                    p->data[i]       = p->data[2*i + 1];                    p->data[2*i + 1] = tmp;                    i                  = 2*i + 1;                }else{                    tmp              = p->data[i];                    p->data[i]       = p->data[2*i];                    p->data[2*i] = tmp;                    i                  = 2*i;                }            }else{                return;            }        }else{            //只有左节点            if (p->data[2*i] > p->data[i])            {                tmp              = p->data[i];                p->data[i]       = p->data[2*i];                p->data[2*i] = tmp;                i                  = 2*i;            }else{                return;            }        }    }}//遍历堆void TraverseArray(struct MaxHeap *p){    if (p != NULL)    {        printf("size:%d \n",p->size);        for (int i = 1; i <= p->size; ++i)        {            printf("%d \n",p->data[i]);        }    }}//校验堆void checkMaxHeap(struct MaxHeap *p){    if (p != NULL)    {        for (int i = 1; i <= p->size; ++i)        {            if (2*i <= p->size)            {                if (p->data[i] < p->data[2*i])                {                    printf("error l %d \n",i);                }            }            if (2*i +1 <= p->size)            {                if (p->data[i] < p->data[2*i +1])                {                    printf("error r %d \n",i);                    for (int j = 0; j <= 2*i +1; ++j)                    {                        printf("error r: %d \n",p->data[j]);                    }                    return;                }            }        }    }}

C语言实现第二种：

#include <stdio.h>#include <stdlib.h>typedef struct MaxHeap {    int *data; //数据域    int size; //长度    int max;//最大长度} MaxHeap;void TraverseArray(struct MaxHeap *p){    if (p != NULL)    {        printf("size:%d \n",p->size);        for (int i = 0; i < p->size; ++i)        {            printf("%d \n",p->data[i]);        }    }}void insert(struct MaxHeap *p, int item){    if (p->size == p->max)    {        printf("******:\n");        return;    }    int i = p->size++;    for (; i > 0 && p->data[(i-1)/2] < item; i=(i-1)/2)    {        if (i < 1)        {            break;        }        p->data[i] = p->data[(i-1)/2];    }    p->data[i] = item;}void delete(struct MaxHeap *p){    p->data[0] = p->data[--p->size];    int i = 0;    int tmp = 0;    while(2*i + 1 < p->size){        //如果有右节点        if (2*i + 2 < p->size)        {            if (p->data[2*i + 2] > p->data[i] || p->data[2*i + 1] > p->data[i])            {                if (p->data[2*i + 2] > p->data[2*i + 1])                {                    printf("dele r max :%d \n",i);                    tmp              = p->data[i];                    p->data[i]       = p->data[2*i + 2];                    p->data[2*i + 2] = tmp;                    i                  = 2*i + 2;                }else{                    printf("dele l max :%d \n",i);                    tmp              = p->data[i];                    p->data[i]       = p->data[2*i + 1];                    p->data[2*i + 1] = tmp;                    i                  = 2*i + 1;                }            }else{                return;            }        }else{            //只有左节点            if (p->data[2*i + 1] > p->data[i])            {                tmp              = p->data[i];                p->data[i]       = p->data[2*i + 1];                p->data[2*i + 1] = tmp;                i                  = 2*i + 1;            }else{                return;            }        }    }}void checkMaxHeap(struct MaxHeap *p){    if (p != NULL)    {        for (int i = 1; i <= p->size; ++i)        {            if (2*i <= p->size)            {                if (p->data[i] < p->data[2*i + 1])                {                    printf("error l %d \n",i);                }            }            if (2*i +1 <= p->size)            {                if (p->data[i] < p->data[2*i +1])                {                    printf("error r %d \n",i);                    for (int j = 0; j <= 2*i +1; ++j)                    {                        printf("error r: %d \n",p->data[j]);                    }                    return;                }            }        }    }}