数据结构：堆的基本操作及 可以选择大小堆的优化堆

堆是可以理解为特殊的数据结构，每个结点都有一个值。是指二叉堆。堆的特点是根节点的值最小（或最大），且根结点的两个子树也是一个堆堆就是用数组实现的二叉树，所有它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置堆分为大根堆,小根堆,大根堆就是树的根结点值最大，小根堆就是树的根结点值最小。

Heap.h

#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<malloc.h> typedef int DataType; typedef struct Heap { DataType* _array; int _capacity; int _size; }Heap,*pHeap; // 创建堆 void CreateHeap(Heap* hp, DataType* array, int size); // 在堆中插入值为data的元素 void InsertHeap(Heap* hp, DataType data); // 获取堆顶元素 DataType TopHeap(Heap* hp); // 检测一个堆是否为空堆 int EmptyHeap(Heap* hp); // 获取堆中元素的个数 int SizeHeap(Heap* hp); // 删除堆顶元素 void DeleteHeap(Heap* hp); // 销毁堆 void DestroyHeap(Heap* hp); /辅助函数 void AdjustDown(Heap* hp,int parent); void AdjustUp(Heap* hp, int child); void swap(DataType* pleft, DataType* pright); void AdjustUp(Heap* hp, int child); int CheckCapacity(Heap* hp); void print(Heap* hp);

Heap.c

#include"Heap.h" // 创建堆 void CreateHeap(Heap* hp, DataType* array, int size) { int i = 0; int root = ((size - 2) >> 1); //给堆申请空间 hp->_array = (DataType*)malloc(sizeof(DataType) * size); if (NULL == hp->_array) { assert(0); return; } hp->_capacity = size; //放置元素 for (;i < size;i++) { hp->_array[i] = array[i]; } hp->_size = size; //调整 for (;root >= 0;--root) { //向下调整 AdjustDown(hp,root); } } void AdjustDown(Heap* hp, int parent) { //child标记parent结点左右子树中最小的孩子 //默认左孩子最小 int child = parent * 2 + 1; while (hp->_size > child) { //找左右孩子中最小的一个 if (hp->_size > child + 1 && hp->_array[child] > hp->_array[child + 1]) { child += 1; } if (hp->_array[parent] > hp->_array[child]) { swap(&hp->_array[parent],&hp->_array[child]); parent = child; child = parent * 2 + 1; } else { return; } } } void swap(DataType* pleft, DataType* pright) { assert(pleft); assert(pright); DataType tmp; tmp = *pleft; *pleft = *pright; *pright = tmp; } void AdjustUp(Heap* hp, int child) { int parent = (child - 1) >> 1; while (child) { if (hp->_array[parent] > hp->_array[child]) { swap(&hp->_array[parent], &hp->_array[child]); child = parent; parent = (child - 1) >> 1; } else return; } } int CheckCapacity(Heap* hp) { assert(hp); if (hp->_capacity == hp->_size) { //申请新空间 int newCapacity = hp->_capacity * 2; DataType* ptemp = (DataType*)malloc(sizeof(DataType) * newCapacity); if (NULL == ptemp) { assert(0); return 0; } //拷贝元素 for (int i = 0;i < hp->_size;++i) { ptemp[i] = hp->_array[i]; } //释放旧空间 free(hp->_array); hp->_array = ptemp; hp->_capacity = newCapacity; } } // 在堆中插入值为data的元素 void InsertHeap(Heap* hp, DataType data) { //向上调整 assert(hp); //检测容量 CheckCapacity(hp); //插入元素，将待插入元素放置最后一个元素之后 hp->_array[hp->_size++] = data; //重新排序 AdjustUp(hp, hp->_size - 1); } // 获取堆顶元素 DataType TopHeap(Heap* hp) { assert(hp); return hp->_array[0]; } // 检测一个堆是否为空堆 int EmptyHeap(Heap* hp) { assert(hp); return 0 == hp->_size; } // 获取堆中元素的个数 int SizeHeap(Heap* hp) { assert(hp); return hp->_size; } // 删除堆顶元素 void DeleteHeap(Heap* hp) { if (EmptyHeap == NULL) return; swap(&hp->_array[0],&hp->_array[hp->_size - 1]); hp->_size -= 1; AdjustDown(hp,0); } // 销毁堆 void DestroyHeap(Heap* hp) { assert(hp); if (hp->_array) { free(hp->_array); hp->_capacity = 0; hp->_size = 0; } } void print(Heap* hp) { assert(hp); int i = 0; for (;i < hp->_size;i++) { printf("%d->",hp->_array[i]); } printf("\n"); } void test() { Heap hp; int array[] = { 53,17,78,9,45,65,87,23,31 }; CreateHeap(&hp,array,sizeof(array)/sizeof(array[0])); print(&hp); InsertHeap(&hp,24); print(&hp); DeleteHeap(&hp); print(&hp); } int main() { test(); system("pause"); return 0; }

优化：大小堆可选

Heap.h

#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<malloc.h> typedef int DataType; typedef int (*Compare)(DataType left, DataType right);//接受两个指针类型的参数，返回一个整形的函数指针 typedef struct Heap { DataType* _array; int _capacity; int _size; Compare com; }Heap,*pHeap; // 创建堆 void CreateHeap(Heap* hp, DataType* array, int size, Compare com); // 在堆中插入值为data的元素 void InsertHeap(Heap* hp, DataType data); // 检测堆是否为空 int EmptyHeap(Heap* hp); // 获取堆中元素的个数 int SizeHeap(Heap* hp); // 获取堆顶元素 DataType TopHeap(Heap* hp); // 删除堆顶的元素 void DeleteHeap(Heap* hp); // 销毁堆 void DestroyHeap(Heap* hp); // 用于元素比较的比较器 // 小于号 int Less(DataType left, DataType right); // 大于好 int Greater(DataType left, DataType right); /辅助函数 void AdjustDown(Heap* hp,int parent); void AdjustUp(Heap* hp, int child); void swap(DataType* pleft, DataType* pright); void AdjustUp(Heap* hp, int child); int CheckCapacity(Heap* hp); void print(Heap* hp);

Head.c

#include"Heap.h" // 创建堆 void CreateHeap(Heap* hp, DataType* array, int size, Compare com) { int i = 0; int root = ((size - 2) >> 1); //给堆申请空间 hp->_array = (DataType*)malloc(sizeof(DataType) * size); if (NULL == hp->_array) { assert(0); return; } hp->_capacity = size; //放置元素 for (;i < size;i++) { hp->_array[i] = array[i]; } hp->_size = size;//初始化 hp->com = com;//初始化 //调整 for (;root >= 0;--root) { //向下调整 AdjustDown(hp,root); } } void AdjustDown(Heap* hp, int parent) { //child标记parent结点左右子树中最小的孩子 //默认左孩子最小 int child = parent * 2 + 1; while (hp->_size > child) { if (hp->_size > child + 1 && hp->com(hp->_array[child + 1] , hp->_array[child]) ) { child += 1; } if (hp->com(hp->_array[child], hp->_array[parent])) { swap(&hp->_array[parent],&hp->_array[child]); parent = child; child = parent * 2 + 1; } else { return; } } } void swap(DataType* pleft, DataType* pright) { assert(pleft); assert(pright); DataType tmp; tmp = *pleft; *pleft = *pright; *pright = tmp; } void AdjustUp(Heap* hp, int child) { int parent = (child - 1) >> 1; while (child) { if (hp->com(hp->_array[child], hp->_array[parent])) { swap(&hp->_array[parent], &hp->_array[child]); child = parent; parent = (child - 1) >> 1; } else return; } } int CheckCapacity(Heap* hp) { assert(hp); if (hp->_capacity == hp->_size) { //申请新空间 int newCapacity = hp->_capacity * 2; DataType* ptemp = (DataType*)malloc(sizeof(DataType) * newCapacity); if (NULL == ptemp) { assert(0); return 0; } //拷贝元素 for (int i = 0;i < hp->_size;++i) { ptemp[i] = hp->_array[i]; } //释放旧空间 free(hp->_array); hp->_array = ptemp; hp->_capacity = newCapacity; } return 0; } // 在堆中插入值为data的元素 void InsertHeap(Heap* hp, DataType data) { //向上调整 assert(hp); //检测容量 CheckCapacity(hp); //插入元素，将待插入元素放置最后一个元素之后 hp->_array[hp->_size++] = data; //重新排序 AdjustUp(hp, hp->_size - 1); } int Less(DataType left, DataType right) { assert(left); assert(right); return left < right; } // 大于好 int Greater(DataType left, DataType right) { assert(left); assert(right); return left > right; } // 获取堆顶元素 DataType TopHeap(Heap* hp) { assert(hp); return hp->_array[0]; } // 检测一个堆是否为空堆 int EmptyHeap(Heap* hp) { assert(hp); return 0 == hp->_size; } // 获取堆中元素的个数 int SizeHeap(Heap* hp) { assert(hp); return hp->_size; } // 删除堆顶元素 void DeleteHeap(Heap* hp) { if (EmptyHeap == NULL) return; swap(&hp->_array[0],&hp->_array[hp->_size - 1]); hp->_size -= 1; AdjustDown(hp,0); } // 销毁堆 void DestroyHeap(Heap* hp) { assert(hp); if (hp->_array) { free(hp->_array); hp->_capacity = 0; hp->_size = 0; } } void print(Heap* hp) { assert(hp); int i = 0; for (;i < hp->_size;i++) { printf("%d->",hp->_array[i]); } printf("\n"); } void test() { Heap hp; int array[] = { 53,17,78,9,45,65,87,23,31 }; CreateHeap(&hp,array,sizeof(array)/sizeof(array[0]),Greater); print(&hp); CreateHeap(&hp, array, sizeof(array) / sizeof(array[0]), Less); print(&hp); } int main() { test(); system("pause"); return 0;}

优化时使用了函数指针：点击打开链接 点击打开链接 点击打开链接 点击打开链接