注：这里我们所实现的是大根堆（即父节点不小于子节点的堆）

目录

一，堆的介绍

二，堆结构的创建

三，接口实现

1，初始化与销毁

2，数据的插入与删除

3，其他接口

一，堆的介绍

两种结构：

在物理结构上，堆就是一块连续的储存空间，对应数组

在逻辑结构上，堆是一棵完全二叉树

两种形式：

大根堆：父节点不小于子节点

小根堆：父节点不大于子节点

二，堆结构的创建

三个成员，指向数组的指针datas，表示数组中有效数据个数的size，表示数组容量的capacity

typedef int HeapDataType;typedef struct Heap
{HeapDataType* datas;int size;int capacity;
}Heap;

这里如果我们对比堆和顺序表，可以发现结构体的创建可以说是一摸一样的，我想这就体现出了数据结构的精髓在于思想的这点，同一个结构体因为使用方式的不同，从而使它发挥出了不同作用，变成了新的模样。

三，接口实现

1，初始化与销毁

初始化，在使用堆之前，置空堆的成员；

销毁，在使用堆之后，释放空间，置空堆的成员；

void HeapInit(Heap* pHeap);

void HeapInit(Heap* pHeap)
{assert(pHeap != NULL);pHeap->datas = NULL;pHeap->size = pHeap->capacity = 0;
}

void HeapDestroy(Heap* pHeap);

void HeapDestroy(Heap* pHeap)
{assert(pHeap != NULL);free(pHeap->datas);pHeap->datas = NULL;pHeap->size = pHeap->capacity = 0;
}

2，数据的插入与删除

void HeapPush(Heap* pHeap, HeapDataType x);

数据插入前首先检查容量是否足够，不够则需要扩容，空间足够后插入数据，但这时数据的结构可能不满足堆的要求了（大根堆要求父节点不小于子节点，新节点可能不满足这种关系），此时需要调整（这里的调整称为向上调整）

void HeapPush(Heap* pHeap, HeapDataType x)
{assert(pHeap != NULL);HeapCheckCapacity(pHeap);pHeap->datas[pHeap->size] = x;AdjustUp(pHeap->datas, pHeap->size);pHeap->size++;
}

向上调整的做法是首先找到新节点的父节点，通过比较大小来判断是否进行数据的交换（子节点大于父节点则交换，反之不需调整），如果进行了交换还需要继续判断，直到新数据到了合适的位置（满足堆的要求）

void AdjustUp(HeapDataType* datas, int child)
{int parent = (child - 1) / 2;while (child > 0){if (datas[child] > datas[parent]){Swap(&datas[child], &datas[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

void Swap(HeapDataType* x, HeapDataType* y)
{HeapDataType temp = *x;*x = *y;*y = temp;
}
void HeapCheckCapacity(Heap* pHeap)
{if (pHeap->size == pHeap->capacity){int newcapacity = 2 * pHeap->capacity;pHeap->datas = (HeapDataType*)realloc(pHeap->datas, sizeof(HeapDataType) * newcapacity);assert(pHeap->datas != NULL);pHeap->capacity = newcapacity;}
}

void HeapPop(Heap* pHeap); 

注意这里的删除操作，删除的是根节点

堆根节点的删除，首先交换数组首元素和尾元素的数据，然后进行调整（首尾元素数据交换后数据的结构可能不满足堆的要求），这里的调整称为向下调整

void HeapPop(Heap* pHeap)
{assert(pHeap != NULL);assert(HeapEmpty(pHeap) != true);Swap(&(pHeap->datas[0]), &(pHeap->datas[pHeap->size - 1]));pHeap->size--;AdjustDown(pHeap->datas, pHeap->size, 0);
}

与向上调整相似，向下调整的做法是首先找到根节点的子节点（较大的子节点），通过比较大小来判断是否进行数据的交换（子节点大于父节点则交换，反之不需调整），如果进行了交换还需要继续判断，知道根数据到了合适的位置（满足堆的要求） 

void Swap(HeapDataType* x, HeapDataType* y)
{HeapDataType temp = *x;*x = *y;*y = temp;
}
void AdjustDown(HeapDataType* datas, int size, int parent)
{int child = parent * 2 + 1;while (child < size){if (child + 1 < size && datas[child] < datas[child + 1]){child += 1;}if (datas[parent] < datas[child]){Swap(&datas[parent], &datas[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}

3，其他接口

HeapDataType HeapTop(Heap* pHeap);查看根节点数据

HeapDataType HeapTop(Heap* pHeap)
{return pHeap->datas[pHeap->size - 1];
}

bool HeapEmpty(Heap* pHeap);判断堆是否为空

bool HeapEmpty(Heap* pHeap)
{return pHeap->size == 0 ? true : false;
}

int HeapSize(Heap* pHeap);查看堆有效数据的多少

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