堆的创建、优先队列、topk、堆排序C语言实现
1、堆的定义
堆就是用数组实现的二叉树，所有它没有使用父指针或者子指针。
堆就是利用完全二叉树的结构来维护的一维数组。
创建一个堆除了一个简单的一维数组以外，不需要任何额外的空间。
如果我们不允许使用指针，那么我们怎么知道哪一个节点是父节点，哪一个节点是它的子节点呢？节点在数组中的位置index 和它的父节点已经子节点的索引之间有一个映射关系。
如果 i 是某个节点的索引，那么下面的公式就给出了它的父节点和子节点在数组中的位置：
parent(i) = floor((i - 1)/2) left(i) = 2i + 1 right(i) = 2i + 2
注意 right(i) 就是简单的 left(i) + 1。左右节点总是处于相邻的位置。
2、堆的分类
按照堆的特点可以把堆分为大顶堆和小顶堆
大顶堆：每个结点的值都大于或等于其左右孩子结点的值，左右孩子节点无大小关系
小顶堆：每个结点的值都小于或等于其左右孩子结点的值，左右孩子节点无大小关系
我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子
我们用简单的公式来描述一下堆的定义就是：（读者可以对照上图的数组来理解下面两个公式）
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
堆可以用来做什么：
- 构建优先队列
- topk
- 支持堆排序
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<stdio.h> #define MAX 100 typedef struct Heap HeapNode; struct Heap{ int Arr[MAX] ; int Size ; }; void print(HeapNode *heap){ int i = 0; for(;i<heap->Size;i++){ printf("%d ",heap->Arr[i]); } printf(" "); } //创建堆 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<len;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<heap->Size&&(heap->Arr[right] < heap->Arr[left])) min = right; //如果根节点比左右节点中小的那个还小，则不用交换 if(heap->Arr[root]<= heap->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<stdio.h> #define MAX 100 typedef struct Heap HeapNode; struct Heap{ int Arr[MAX] ; int Size ; }; void print(HeapNode *heap){ int i = 0; for(;i<heap->Size;i++){ printf("%d ",heap->Arr[i]); } printf(" "); } //创建堆 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<len;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<heap->Size&& (heap->Arr[right] < heap->Arr[left])) min = right; //如果根节点比左右节点中小的那个还小，则不用交换 if(heap->Arr[root]<= heap->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]<=heap->Arr[now]){ break ; } printf("%d:%d ",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<stdio.h> #define MAX 100 typedef struct Heap HeapNode; struct Heap{ int Arr[MAX] ; int Size ; }; void print(HeapNode *heap){ int i = 0; for(;i<heap->Size;i++){ printf("%d ",heap->Arr[i]); } printf(" "); } //创建堆 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<len;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<heap->Size&& (heap->Arr[right] < heap->Arr[left])) min = right; //如果根节点比左右节点中小的那个还小，则不用交换 if(heap->Arr[root]<= heap->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 <= heap->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; }