小堆的结构与初始化
小堆的结构是子节点不小于父节点，兄弟结点没有顺序，并且总是完全二叉树。
逻辑结构是这样的：
物理储存我们用顺序表来储存：
首先从结点的祖先10开始，放进顺序表中，然后是他的子节点15和20，再往下访问也是访问15和20的子节点，分别是30，20，25，90，按照这个规律放进顺序表中就可以了。
[10,15,20,30,20,25,90,40,30,70];
首先创建一个顺序表的结构体
typedef int SD;//方便以后更改数组的数据类型 typedef struct pile { SD* a;//数组 int size;//数组有效值的长度 int capacity;//数组容量大小 }pile;
初始化
void initialize(pile* hp)//初始化 { hp->a = NULL; hp->capacity = hp->size = 0; }
堆的销毁，空判定，打印
销毁
void HeapDestory(pile* hp)//销毁 { free(hp->a); hp->a = NULL; hp->capacity = hp->size = 0; }
判断是否为空
空返回0，非空返回非0.
int HeapEmpty(pile* hp)//判断空 { return hp->size; }
打印
这里只打印整理后的数组：
void Pintf(pile* hp)//打印 { assert(hp); int i = 0; for (i = 0; i < hp->size; i++) { printf("%d ", hp->a[i]); } }
插入，删除
插入
物理结构是在顺序表中末尾插入一个数据。
比如说我们插入一个5.
但是如果插入之后就不是小堆的结构了，祖先不小于等于新增元素，所以我们需要将5向上调整。（红线是调整顺序）
调成之后是这样的：
void swap(SD* p1,SD* p2)//交换数据 { SD p = *p1; *p1 = *p2; *p2 = p; } void HeapPush(pile* hp, SD x)//插入 { assert(hp); if (hp->capacity == hp->size) { int sum = hp->capacity == 0 ? 4 : hp->capacity * 2; SD* p = (SD* )realloc(hp->a, sum * sizeof(SD)); if (p == NULL) { perror("realloc fail"); exit(-1); } hp->a = p; hp->capacity = sum; } hp->a[hp->size] = x;//插入数据 hp->size++;//记录数组的有效长度 int child = hp->size - 1;//新插入的元素,元素的下标 int parent = (child - 1) / 2;//新插入的元素的父节点,父节点的下标 while (child > 0)//孩子的下标如果等于0就说明到堆顶了 { if (hp->a[child] < hp->a[parent])//如果孩子比父节点小就交换 { swap(&(hp->a[child]), &(hp->a[parent]));//交换 child = parent; parent = (child - 1) / 2; } else { break;//如果不成立就说明已经是小堆了 } } }
删除
删除第一个元素。
因为要保持原来小堆的形态，所以要让10到删除的那个位置，20不行，然后是15补刀10的位置，以此类推。（向下调整算法）
最后变成了这样：
代码是这个操作我们需要将头和尾先交换一下，然后删除尾再向下调整。
void HeapPop(pile* hp)//删除 { assert(hp); assert(HeapEmpty(hp));//判断是否为空 swap(&hp->a[hp->size - 1], &hp->a[0]);//交换首尾的位置 hp->size-- ;//删掉末尾的数 int parent = 0;//父结点下标 int minchild = 2 * parent + 1;//表示最小的孩子，第一次先假设左孩子最小 while (minchild < hp->size)//防止数组越界 { if (minchild+1 < hp->size && hp->a[minchild + 1] < hp->a[minchild])//防止右孩子出界 { minchild = minchild++;//如果右孩子比左孩子小就让右孩子等于最小 } if (hp->a[minchild] < hp->a[parent])//判断是否需要向下调整 { swap(&hp->a[minchild], &hp->a[parent]); parent = minchild; minchild = 2 * parent + 1; } else { break; } } }
