在前面的学习中，我们已经学习了数据结构中的顺序表，链表，栈，队列。这些数据结构都是线性数据结构，从这篇文章开始，我们将要研究树这种非线性数据结构。
堆的介绍
首先介绍一下什么是树
树是有限个节点构成的具有层次关系的集合。因为这种关系的逻辑图看起来像一颗倒挂的树，故叫做树。
其次介绍一下树的种类
树又分为二叉树和非二叉树，二叉树又分为完全二叉树和满二叉树。这篇文章主要详细介绍堆，堆是一种完全二叉树。
其次介绍一下堆的种类
堆又分为大堆，小堆。大堆：父节点大于等于子节点 小堆：父节点小于等于子节点
堆的实现
堆的实现：堆的逻辑结构是完全二叉树，存储结构是顺序结构。下面以小堆的实现为例。
要实现堆，首先明白堆的逻辑结构是完全二叉树，存储结构是顺序表。
在完全二叉树中，有如下结论
父节点找左孩子：parent*2+1
父节点找右孩子：parent*2+2
孩子找父节点：(child-1)/2
heap.h
heap.c
堆的初始化
1. void IntiHeap(Hp* heap) 2. { 3. assert(heap); 4. //malloc一块空间,用来初始化顺序表 5. DateType* tmp = (DateType*)malloc(4 * sizeof(DateType)); 6. assert(tmp);//保证malloc成功 7. heap->arr = tmp;//初始化顺序表 8. heap->size = 0;//有效数据个数0 9. heap->capcity = 4;//初始容量4 10. }
堆的销毁
1. void DestoryHeap(Hp* heap) 2. { 3. assert(heap); 4. free(heap->arr);//释放顺序表空间 5. heap->arr = NULL;//将指针置空，避免成为野指针 6. heap->size = 0;//有效数据置0 7. heap->capcity = 0;//容量置0 8. }
堆的插入
堆的插入是这里的关键，这里以小堆为例，欲在小堆里插入一个元素，这里的步骤为：
step1.直接插入到堆尾 step2.向上调整。
1. void HeapPush(Hp* heap, DateType n) 2. { 3. assert(heap); 4. if (heap->size == heap->capcity)//检查容量 5. { 6. //扩容 7. DateType* tmp = realloc(heap->arr, 2 * heap->capcity * sizeof(DateType)); 8. assert(tmp); 9. heap->arr = tmp; 10. heap->capcity *= 2; 11. } 12. //直接插入，未做调整step1 13. heap->arr[heap->size] = n; 14. heap->size++; 15. //向上调整step2 16. UpAdjust(heap->arr, heap->size - 1);//参数为堆的存储顺序表和堆尾节点下标（孩子） 17. }
向上调整算法
1. void UpAdjust(DateType* arr, int child)//向上调整算法 2. { 3. int parent = (child - 1) / 2;//找到父亲节点 4. while (child != 0)//直到child成为0,不需要向上调整 5. { 6. if (arr[child] < arr[parent])//如果不满足小堆定义 7. { 8. //交换 9. swap(&arr[child],&arr[parent]); 10. } 11. else//满足就不需要向上调整了 12. { 13. break; 14. } 15. //向上迭代child,parent 16. child = parent; 17. parent = (child - 1) / 2; 18. } 19. }
堆顶元素删除
堆顶元素删除的步骤为：
step1.交换堆顶元素和堆尾元素，直接删除堆尾元素 step2.向下调整堆。
1. void HeapPop(Hp* heap) 2. { 3. assert(heap); 4. assert(!HeapEmpty(heap));//保证堆不为空 5. //step1:先交换，再size--，再调整堆 6. swap(&heap->arr[0], &heap->arr[heap->size - 1]); 7. heap->size--; 8. //step2:调堆，向下调整算法 9. DownAdjust(heap->arr, heap->size, 0); 10. }
向下调整算法：
step2
1. //堆的存储结构 堆的有效数据个数 向下调整起始父节点 2. void DownAdjust(DateType* arr, int size, int parent) 3. { 4. int child = parent * 2 + 1;//找到左孩子 5. while (child<size) 6. { 7. //防止没有右孩子，越界 8. if (child+1<size&&arr[child] > arr[child + 1])//调整并找到数据较小的child 9. { 10. child++;//由左孩子变为右孩子 11. } 12. 13. if (arr[child] < arr[parent])//如果不满足小堆定义 14. { 15. swap(&arr[child], &arr[parent]);//交换 16. //迭代 17. parent = child; 18. child = parent * 2 + 1; 19. } 20. else 21. { 22. break; 23. } 24. } 25. }
判断堆是否为空
1. bool HeapEmpty(Hp* heap) 2. { 3. assert(heap); 4. return heap->size == 0; 5. }
获取堆顶元素
1. DateType TopHeap(Hp* heap) 2. { 3. assert(heap); 4. return heap->arr[0]; 5. }
获取堆有效数据
1. int HeapSize(Hp* heap) 2. { 3. return heap->size; 4. }
