堆的创建、优先队列、topk、堆排序C语言实现
2021-05-12 23:30
阅读：554
3、堆和普通树的区别
堆并不能取代二叉搜索树，它们之间有相似之处也有一些不同。我们来看一下两者的主要差别：
节点的顺序：在二叉搜索树中，左子节点必须比父节点小，右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。
内存占用：普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配额为是我内存。堆仅仅使用一个数据来村塾数组，且不使用指针。
平衡：二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足对属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。
搜索：在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。
4、堆的操作
创建堆:创建小顶堆
1.将数组顺序添加到堆中。（此时堆还不算小顶堆）
2.调整堆为小顶堆
注意：
1.for(j=(heap->Size-1)/2;j>=0;j--)：比如我下面堆中有十个元素，Size大小也为10，第一次调整堆时，索引是从4开始的，那么它的左右节点分别是：9、10索引位置上的元素，很明显，10索引是不存在。
j的数字依次是4，3，2，1，0。
2.每次外层遍历都需要判断节点的左右节点是否存在（左节点存在，右节点自然存在，左右节点相邻，右节点索引=左节点索引+1）,然后找出左右节点中的最小值，节点与此最小值交换，最后索引位置也交换，继续往下
#include#define MAX 100 typedef struct Heap HeapNode; struct Heap{ int Arr[MAX] ; int Size ; }; void print(HeapNode *heap){ int i = 0; for(;i Size;i++){ printf("%d ",heap->Arr[i]); } printf("\n"); } //创建堆 HeapNode * create(){ HeapNode *heap; heap = (HeapNode*)malloc(sizeof(HeapNode)); heap->Size = 0; return heap; } //向堆中添加数据并调整为最小堆 void Add_and_Adjust(HeapNode * heap,int arr[],int len){ //添加数组元素到堆，顺序添加就可以了 int i =0; for(0;i ){ heap->Arr[i] = arr[i]; } //赋值堆的成员个数：用于处理左右节点是否存在的判断 heap->Size = i; //调整堆为最小堆：自下往上 int j = 0; for(j=(heap->Size-1)/2;j>=0;j--){ adjust(heap,j); print(heap); } } //自上往下 void adjust(HeapNode * heap,int root){ while(1){ int left = 2 * root + 1; int right = 2 * root + 2; //判断此节点的左右节点是否存在：如果左边的left都不存在，则右节点也不会存在，则该节点没有左右节点 //通过索引位置判断 if(left>=heap->Size){ return ; } //我们需要找到左右节点中的最小值 //假设左节点为最小值 int min = left; //如果右节点存在，且右节点的值小于左节点，则右节点为最小值 if(right Size&&(heap->Arr[right] Arr[left])) min = right; //如果根节点比左右节点中小的那个还小，则不用交换 if(heap->Arr[root]Arr[min]) return ; //如果根节点比左右节点中小的大，则交换 int temp = heap->Arr[root]; heap->Arr[root] = heap->Arr[min]; heap->Arr[min] = temp; //交换后，继续往下遍历，根索引位置等于左右节点中值小些的索引 root = min; } } int main(void) { int arr[10] = {76,23,43,6,87,56,34,45,32,12}; HeapNode *heap = create(); Add_and_Adjust(heap,arr,10); return 0; }
构建优先队列：利用堆的堆顶为最小值或者最大值的特性
需要掌握堆的插入操作：需要注意的是每次插到数组末尾，从末尾与父节点比较交换，交换后，继续往上比较，直至没有满足比较条件或者到达索引为1的节点。
1.每次插入一个元素放在堆的数组末尾
2.从末尾开始，与此元素的父节点比较，交换。
#include#define MAX 100 typedef struct Heap HeapNode; struct Heap{ int Arr[MAX] ; int Size ; }; void print(HeapNode *heap){ int i = 0; for(;i Size;i++){ printf("%d ",heap->Arr[i]); } printf("\n"); } //创建堆 HeapNode * create(){ HeapNode *heap; heap = (HeapNode*)malloc(sizeof(HeapNode)); heap->Size = 0; return heap; } //向堆中添加数据并调整为最小堆 void Add_and_Adjust(HeapNode * heap,int arr[],int len){ //添加数组元素到堆，顺序添加就可以了 int i =0; for(0;i ){ heap->Arr[i] = arr[i]; } //赋值堆的成员个数：用于处理左右节点是否存在的判断 heap->Size = i; //调整堆为最小堆 int j = 0; for(j=(heap->Size-1)/2;j>=0;j--){ adjust(heap,j); print(heap); } } //从顶至下 void adjust(HeapNode * heap,int root){ while(1){ int left = 2 * root + 1; int right = 2 * root + 2; //判断此节点的左右节点是否存在：如果左边的left都不存在，则右节点也不会存在，则该节点没有左右节点 //通过索引位置判断 if(left>=heap->Size){ return ; } //我们需要找到左右节点中的最小值 //假设左节点为最小值 int min = left; //如果右节点存在，且右节点的值小于左节点，则右节点为最小值 if(right Size&& (heap->Arr[right] Arr[left])) min = right; //如果根节点比左右节点中小的那个还小，则不用交换 if(heap->Arr[root]Arr[min]) return ; //如果根节点比左右节点中小的大，则交换 int temp = heap->Arr[root]; heap->Arr[root] = heap->Arr[min]; heap->Arr[min] = temp; //交换后，继续往下遍历，根索引位置等于左右节点中值小些的索引 root = min; } } void insert(HeapNode * heap,int node){ if(heap->Size>=MAX){ return ; } heap->Arr[heap->Size] = node; heap->Size ++; int now = heap->Size-1; print(heap); while(now>=1){ //找到父节点 int root = (now -1)/2; //如果父节点小于此节点，结束 if(heap->Arr[root]Arr[now]){ break ; } printf("%d:%d\n",heap->Arr[root],heap->Arr[now]); //交换 int temp = heap->Arr[root]; heap->Arr[root] = heap->Arr[now]; heap->Arr[now] = temp; //继续往上交换 now = root; } } int main(void) { int arr[10] = {76,23,43,6,87,56,34,45,32,12}; HeapNode *heap = create(); Add_and_Adjust(heap,arr,10); insert(heap,2); print(heap); return 0; }
TOPk
很常见的面试题，利用堆很容易做出来。
找出最大的k个数,我们可以用最小堆来做，
新插入的元素与堆顶的元素比较，如果比它大，则将它赋值给堆顶元素，并向下调整堆（继续维持最小堆的状态），如果比堆顶元素小，则不做处理。
#include#define MAX 100 typedef struct Heap HeapNode; struct Heap{ int Arr[MAX] ; int Size ; }; void print(HeapNode *heap){ int i = 0; for(;i Size;i++){ printf("%d ",heap->Arr[i]); } printf("\n"); } //创建堆 HeapNode * create(){ HeapNode *heap; heap = (HeapNode*)malloc(sizeof(HeapNode)); heap->Size = 0; return heap; } //向堆中添加数据并调整为最小堆 void Add_and_Adjust(HeapNode * heap,int arr[],int len){ //添加数组元素到堆，顺序添加就可以了 int i =0; for(0;i ){ heap->Arr[i] = arr[i]; } //赋值堆的成员个数：用于处理左右节点是否存在的判断 heap->Size = i; //调整堆为最小堆 int j = 0; for(j=(heap->Size-1)/2;j>=0;j--){ adjust(heap,j); } } //从顶至下 void adjust(HeapNode * heap,int root){ while(1){ int left = 2 * root + 1; int right = 2 * root + 2; //判断此节点的左右节点是否存在：如果左边的left都不存在，则右节点也不会存在，则该节点没有左右节点 //通过索引位置判断 if(left>=heap->Size){ return ; } //我们需要找到左右节点中的最小值 //假设左节点为最小值 int min = left; //如果右节点存在，且右节点的值小于左节点，则右节点为最小值 if(right Size&& (heap->Arr[right] Arr[left])) min = right; //如果根节点比左右节点中小的那个还小，则不用交换 if(heap->Arr[root]Arr[min]) return ; //如果根节点比左右节点中小的大，则交换 int temp = heap->Arr[root]; heap->Arr[root] = heap->Arr[min]; heap->Arr[min] = temp; //交换后，继续往下遍历，根索引位置等于左右节点中值小些的索引 root = min; } } void add(HeapNode * heap,int node){ if(node Arr[0] ){ return ; } heap->Arr[0]= node; adjust(heap,0); } int main(void) { int arr[10] = {76,23,43,6,87,56,34,45,32,12}; HeapNode *heap = create(); Add_and_Adjust(heap,arr,10); add(heap,59); add(heap,98); add(heap,349); add(heap,321); add(heap,125); print(heap); return 0; }
上一篇：C++ 定位new创建对象
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：堆的创建、优先队列、topk、堆排序C语言实现
文章链接：http://soscw.com/index.php/essay/84907.html
文章标题：堆的创建、优先队列、topk、堆排序C语言实现
文章链接：http://soscw.com/index.php/essay/84907.html
评论
亲，登录后才可以留言！