c语言实现顺序结构的存储二叉树堆

堆是一个完全二叉树，堆分两种，一种为小堆，一种为大堆 小堆是指对于这个树的任意任意一个子树来说，子树的根节点都要小于左右孩子节点的值，小堆的根节点是这个树的最小元素，每条路径上的节点都是递增的 大堆是指对于这个树的任意任意一个子树来说，子树的根节点都要大于左右孩子节点的值，大堆的根节点是这个树的最大元素，每条路径上的节点都是递减的 堆的结构定义如下： 其中compare函数用来缺点创建的是大堆还是小堆，Greater选择创建大堆，Less选择创建小堆

#pragma once typedef int HPDataType; typedef int(*PCOM) (HPDataType, HPDataType); int Less(HPDataType left, HPDataType right); int Greater(HPDataType left, HPDataType right); typedef struct Heap { HPDataType * _array; HPDataType _capacity; HPDataType _size; PCOM compare; }Heap; void InitHeap(Heap* hp, HPDataType* array, int size, PCOM compare); void InitEmptyHeap(Heap* hp, int capacity, PCOM compare); void InsertHeap(Heap* hp, HPDataType data); void EraseHeap(Heap* hp); int HeapSize(Heap* hp); int HeapEmpty(Heap* hp); HPDataType HeapTop(Heap* hp); void DestroyHeap(Heap* hp);

堆的初始化

void AdjustDown(Heap* hp, size_t index) { assert(hp); size_t parent = index; size_t child = 2 * index + 1; while (child < hp->_size) { if ((child + 1 < hp->_size) && hp->compare(hp->_array[child] ,hp->_array[child + 1])) { child = child + 1; //判断左子树合适还是右子树合适； } if (hp->compare(hp->_array[parent] , hp->_array[child])) { swap(&hp->_array[parent], &hp->_array[child]); } parent = child; child = 2 * parent + 1; } } void InitHeap(Heap* hp, HPDataType* array, int size,PCOM compare) { assert(hp); HPDataType* _arr = (HPDataType*)malloc(sizeof(HPDataType)*size); if (_arr == NULL) { assert(0); return NULL; } hp->_array = _arr; for (int i = 0; i<size; ++i) { hp->_array[i] = array[i]; } hp->_capacity = size; hp->_size = size; hp->compare = compare; } //创建一个堆结构 void CreatHeap(Heap* hp) { assert(hp); for (int dep = (hp->_size - 1) / 2; dep >= 0; --dep) { AdjustDown(hp, dep); } }

查看堆顶元素，查看堆成员个数等操作

//取堆顶元素 HPDataType HeapTop(Heap* hp) { assert(hp); if (hp->_size == 0) { return; } return hp->_array[0]; } //删除堆顶操作操作 void EraseHeap(Heap *hp) { assert(hp); if (hp->_size == 0) { return NULL; } swap(&hp->_array[0], &hp->_array[hp->_size - 1]); hp->_size--; AdjustDown(hp, 0); } int HeapSize(Heap* hp) { assert(hp); return hp->_size; } int HeapEmpty(Heap* hp) { assert(hp); if (!hp->_size) { return 1; } return 0; } HPDataType Head_Is_Full(Heap* hp) { assert(hp); if (hp->_capacity == hp->_size) { return 1; } return 0; } //在堆中插入值为Data的元素 void InsertHeap(Heap* hp, HPDataType data) { assert(hp); //容量不够，进行扩容 if (Head_Is_Full) { int newcapacity = hp->_capacity * 2; HPDataType * newarr = (HPDataType *)malloc(sizeof(HPDataType) * newcapacity); if (newarr == NULL) { assert(0); return NULL; } for (int i = 0; i < hp->_size; ++i) { newarr[i] = hp->_array[i]; } hp->_array = newarr; hp->_capacity = newcapacity; } hp->_array[hp->_size] = data; CreatHeap(hp); hp->_size++; } void DestroyHeap(Heap* hp) { assert(hp); free(hp->_array); hp->_capacity = 0; hp->_size = 0; }

实现堆排序，解决TOP k问题 Greater为升序排列 Less为降序排列

void SortHeap(HPDataType *_arr, size_t size) { Heap hp; InitHeap(&hp, _arr, size,Greater); CreatHeap(&hp); for (int i = 0; i < size; ++i) { EraseHeap(&hp); } hp._size = size; //升序取前5个数 for (int i = size-1; i >= 0; --i) { printf("%d ", hp._array[i]); } DestroyHeap(&hp); } int main() { int _arr[] = { 8,7,6,5,1,3,6,8,9,0,2,11,15,17,19 }; int size = sizeof(_arr) / sizeof(_arr[0]); SortHeap(_arr, size); system("pause"); return 0; }