用数组实现最大 / 小堆，有两种形式，一种是 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;
}
}
}
}
}