前言

        堆是一种重要的数据结构，堆分为大根堆和小根堆，大根堆堆顶的数据是最大的，小根堆堆顶的数据是最小的，堆在逻辑结构上是一颗完全二叉树，这棵树中如果满足根节点大于左右子树，每个节点都满足这个条件就是大根堆，反之就是小根堆。

1.堆的概念和性质

        堆标准的概念是：如果有一个关键码的集合K = {k0,k1,k2,...,kn-1}，把它的所有元素按照完全二叉树的顺序存储方式存储在一个数组中，并且满足： i = 0,1,2..,则称为小堆（或大堆）。将根节点最大的堆称为最大堆或者大根堆，根节点最小的堆叫做最小堆或者小根堆。 

         堆的性质：

        1.堆中某个节点的值总是不大于或者不小于其父节点的值

        2.堆是一颗完全二叉树

        从堆是一颗完全二叉树来理解堆是更容易理解的。

  

2.堆的实现

        2.1向下调整算法

        现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过根节点开始的向下调整算法可以把它调整为一个小堆。向下调整算法的前提是左右子树都必须是小堆，才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

         

        2.2堆的创建

        下面我们给出一个数组，这个数组在逻辑上可以看出一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点的左右子树不是堆，我们怎么调整呢？我们可以从叶子节点开始调整，但是没有必要，因为每个叶子结点都可以看成一个堆。我们可以从倒数第一个非叶子节点开始调整，一直调整到根节点的树，就可以调成一个堆。 

        int a[] = {1,5,3,8,7,6};

          

        2.3建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明（时间复杂度本来看的就是近似值） ，多几个节点没有影响）：

        假设树的高度为h

        第一层有2的零次方个节点，需要向下移动h - 1层

        第二层有2的一次方个节点，需要向下移动h - 2层

        第三层有2的二次方个节点，需要向下移动h - 3层

        第四层有2的三次方个节点，需要向下移动h - 4层

        第h - 1层有2的h - 2次方个节点，需要向下移动1层

        则需要移动节点总的移动步数为：

        因此:建堆的时间复杂度为O(N)

        2.4堆的插入

        堆的插入要插入到数组的末尾，在进行向上调整算法，直到满足堆的特性。

  

        2.5堆的删除

        删除堆，删除的是堆顶的元素，如果直接删除好吗？

        答案是否定的，直接删除堆顶的数据，这个堆就废了，需要重新建堆，所以正确的操作是运用先交换堆顶和堆最后一个元素，进行一次向下调整即可解决问题。 

        2.6堆的代码实现

        //Heap.h

#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
#include<stdbool.h>
#include<string.h>
typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;//存储数据int _size;int _capacity;
}Heap;
void HeapSort(int* a, int size);//堆排序
void ADJustDown(HPDataType* a, int root, int size);//向下调整算法void HeapInit(Heap* php, HPDataType* a, int n);//初始化堆void HeapDestory(Heap* php);//销毁队void HeapPush(Heap* php, HPDataType x);//在堆里面入数据void HeapPop(Heap* php);//出堆顶的数据HPDataType HeapTop(Heap* php);//获取堆顶的数据

        //Heap.c 

#include"Heap.h"
void ADJustDown(HPDataType* a, int root, int size);//向下调整算法void Swap(HPDataType* left, HPDataType* right)
{HPDataType tmp = *left;*left = *right;*right = tmp;
}
void HeapSort(int* a, int size)//堆排序
{//建堆int root = (size - 1 - 1) / 2;//找到非叶子结点while (root >= 0){ADJustDown(a, root, size);--root;}//将堆顶的数据与堆底的数据交换int end = size - 1;while (end > 0){Swap(&a[0], &a[end]);//向下调整ADJustDown(a, 0, end);end--;}
}
void ADJustDown(HPDataType * a,int root, int size)//向下调整算法
{assert(a);//指针存在int parent = root;int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child + 1] < a[child])//找出左右孩子中小的那个孩子{++child;}if (a[child] < a[parent])//交换孩子和父亲{Swap(&a[child], &a[parent]);//迭代继续parent = child;child = parent * 2 + 1;}else{break;//不需要调整}}
}
void ADJustUp(HPDataType* a, int child)//向上调整算法
{assert(a);//确保指针有效int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);//交换父子节点//迭代向后走child = parent;parent = (child - 1) / 2;}else{//结束调整break;}}
}void HeapInit(Heap* php, HPDataType* a, int n)//初始化堆
{php->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);php->_capacity = php->_size = n;memcpy(php->_a, a, sizeof(HPDataType)*n);//建队=堆int root = (n - 1 - 1) / 2;//找到非叶子结点while(root >= 0){ADJustDown(php->_a, root, n);--root;}
}
void HeapDestory(Heap* php)//销毁队
{assert(php);//堆存在free(php->_a);php->_size = php->_capacity = 0;
}
void HeapPush(Heap* php, HPDataType x)//在堆里面入数据
{//判断是不是需不需要增容if (php->_capacity == php->_size){php->_capacity *= 2;HPDataType* tmp = (HPDataType*)realloc(php->_a, sizeof(HPDataType) * php->_capacity);if (tmp == NULL){printf("申请内存失败\n");exit(-1);}php->_a = tmp;}//插入数据php->_a[php->_size] = x;php->_size++;//向上调整ADJustUp(php->_a, php->_size - 1);
}
void HeapPop(Heap* php)//出堆顶的数据
{assert(php);//确保堆不为空assert(php->_size > 0);//确保堆里面存在数据//为了保持堆的特性，需要先将堆顶的数据与堆底的数据交换,然后pop调堆底的数据//在对堆顶开始进行一次向下调整if (php->_size > 1){Swap(&php->_a[0], &php->_a[php->_size - 1]);php->_size--;ADJustDown(php->_a, 0, php->_size);}else if (php->_size == 1){php->_size--;}
}
HPDataType HeapTop(Heap* php)//获取堆顶的数据
{assert(php);//指针存在assert(php->_size > 0);//堆里面有数据return php->_a[0];
}

3.堆的应用

        3.1堆排序

        堆序，即利用堆的思想进行排序，总共分为两个步骤：

        1.建堆

        如果是排升序，是建大堆还是小堆呢？ 如果是排降序呢？

        如果排升序，建小堆的话，每次选出最小的数以后，整个堆就不能用来，就要重新建堆，所以，排升序要建大堆，每次选出最大的数放在数组的最后，堆的大小减一，调用一次向下调整就可以再选出堆里面最大的数了。利用这样的方法就可以实现堆排序了。 

        2.利用堆删除的思想进行排序

        建堆和堆删除中都用到了向下调整算法，因此掌握了向下调整算法就掌握了和堆相关的大部分内容了 ，堆就是这么简单又朴实无华，哈哈哈哈。

 

        

void HeapSort(int* a, int size)//堆排序
{//建堆int root = (size - 1 - 1) / 2;//找到非叶子结点while (root >= 0){ADJustDown(a, root, size);//调用向下调整算法--root;}//将堆顶的数据与堆底的数据交换int end = size - 1;while (end > 0){Swap(&a[0], &a[end]);//向下调整ADJustDown(a, 0, end);end--;}
}
void ADJustDown(HPDataType * a,int root, int size)//向下调整算法
{assert(a);//指针存在int parent = root;int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child + 1] < a[child])//找出左右孩子中小的那个孩子{++child;}if (a[child] < a[parent])//交换孩子和父亲{Swap(&a[child], &a[parent]);//迭代继续parent = child;child = parent * 2 + 1;}else{break;//不需要调整}}
}

        3.2TOP-K问题

         TOP-K问题：即求数据集合中前k个最大或者最小的元素，一般情况下数据量会很大。

        比如：专业前10名，世界500强，富豪榜，游戏中前100的活跃玩家等等。

        对于TOP-K问题，能想到的最简单的方式就是排序，但是如果数据量很大，排序就不太可取了（数据可能无法加载到内存中，数据太多了）。最佳的解决方式就是用堆来解决，基本思路如下：

        1.用数据前K个元素来建堆

        如果是求前K大的数，就建一个小堆，如果堆顶的数比剩下的数小就替换堆顶的数据。直到比较完所有的数据。

        如果是求前K小的数据，就建一个大堆，如果堆顶的数比剩下的数大就将堆顶的数替换为正在比较的数，直到比较完所有的数据。

        形象一点来说堆顶数就像是守门员一样，到最后堆顶的数肯定是前K小的数或者前K大数。

        2.用剩余的K-N个元素来和堆顶的数据进行比较，不满足则替换堆顶的元素

将剩余N-K个元素依次与堆顶的元素比较完后，堆里面剩余的K个元素就是所求的前K个最小或者最大的元素。 

        它的时间复杂度是N*log（K）。 

        TOP-K问题

        代码：

void Swap(int* left, int* right)
{int tmp = *left;*left = *right;*right = tmp;
}
void AdJustDown(int* a,int root, int size)//向下调整算法
{assert(a);//指针存在int parent = root;int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child + 1] < a[child])//找出左右孩子中小的那个孩子{++child;}if (a[child] < a[parent])//交换孩子和父亲{Swap(&a[child], &a[parent]);//迭代继续parent = child;child = parent * 2 + 1;}else{break;//不需要调整}}
}
int findKthLargest(int* nums, int numsSize, int k)
{//使用向下调整算法进行建堆int root = (k - 1) / 2;//找到倒数第一个非叶子节点while(root >= 0)//对前k个数组元素建小堆{AdJustDown(nums, root, k);--root;}for(int i = k; i < numsSize; ++i){if(nums[0] < nums[i]){//取代堆顶的数据，进行向下调整int tmp = nums[0];nums[0] = nums[i];nums[i] = tmp;AdJustDown(nums, 0, k);}}for(int i = 0; i < numsSize; ++i){printf("%d ",nums[i]);}return nums[0];//此时堆顶的元素就是第K大的元素
}