数据结构【堆的概念及接口实现】

1.关于堆你应该知道的？

堆是一棵完全二叉树，堆中的元素存储在一个一维数组中，对于任意节点，如果该节点小于其左右孩子，我们把这种结构叫做小堆；如果大于其左右孩子，我们把这种结构叫做大堆。

堆的特性：

堆顶元素一定是堆中所有元素最大（最小）的堆总是一棵完全二叉树堆中的某个节点的值一定是不大于或者不小于其父节点的值

2. C语言实现堆的接口

typedef int HPDataType; typedef struct Heap { HPDataType* _array; int _capacity; int _size; }Heap; void Swap(HPDataType* x, HPDataType* y) { HPDataType temp = *x; *x = *y; *y = temp; } void CheckCapacity(Heap* hp) { assert(hp); if (hp->_size == hp->_capacity) { int newCapacity = hp->_capacity * 2; HPDataType* pTemp = (HPDataType*)malloc(sizeof(HPDataType)*newCapacity); if (NULL == pTemp) { assert(0); return; } for (int i = 0; i < hp->_size; i++) { pTemp[i] = hp->_array[i]; } free(hp->_array); hp->_capacity = newCapacity; hp->_array = pTemp; } } //堆向下调整算法 void AdjustDown(HPDataType* array, int size, int parent) { //默认用child标记parent的左孩子，完全二叉树只有一个孩子的话，一定是左孩子 int child = parent * 2 + 1; //找双亲孩子中较小的孩子 while (child < size){ if (child + 1 < size && array[child + 1] < array[child]) { child += 1; } if (array[child] < array[parent]) { Swap(&array[child], &array[parent]); parent = child; child = parent * 2 + 1; } else { return; } } } //堆向上调整算法 void ADjustUP(HPDataType* array, int size, int child) { int parent = (child - 1) / 2; while (child) { if (array[child] < array[parent]) { Swap(&array[child], &array[parent]); child = parent; parent = (child - 1) / 2; } else { return; } } } //空堆的初始化 void InitEmptyHeap(Heap* hp,int capacity) { assert(hp); hp->_array = (HPDataType*)malloc(sizeof(HPDataType)*capacity); if (NULL == hp->_array) { assert(0); return; } hp->_capacity = capacity; hp->_size = 0; } //堆的初始化 void InitHeap(Heap* hp, HPDataType* array, int size) { assert(hp); hp->_array = (HPDataType*)malloc(sizeof(HPDataType)*size); if (NULL == hp->_array) { assert(0); return; } hp->_capacity = size; for (int i = 0; i < size; i++) { hp->_array[i] = array[i]; } hp->_size = size; //找到最后一个非叶子节点 int root = (size - 2) / 2; for (; root >= 0; root--){ AdjustDown(hp->_array, size, root); } } //在堆中插入元素 void InsertHeap(Heap* hp, HPDataType* data) { CheckCapacity(&hp); hp->_array[hp->_size] = data; hp->_size++; ADjustUP(hp->_array, hp->_size, hp->_size - 1); } //删除一个堆元素 void EarseHeap(Heap* hp) { if (HeapEmpty(hp)) return; Swap(&hp->_array[0], &hp->_array[hp->_size - 1]); hp->_size -= 1; AdjustDown(hp->_array, hp->_size, 0); } //获取堆中有效元素个数 int HeapSize(Heap* hp) { assert(hp); return hp->_size; } //判断堆是否为空 int HeapEmpty(Heap* hp) { assert(hp); return 0 == hp->_size; } //获取堆顶元素 HPDataType HeapTop(Heap* hp) { assert(hp); return hp->_array[0]; } //销毁堆 void DestroyHeap(Heap* hp) { assert(hp); if (hp->_array) { free(hp->_array); hp->_capacity = 0; hp->_size = 0; } }