关于数据结构:数据结构与算法-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;
                }
            }
        }
    }
}