什么是堆
把所有的元素按照完全二叉树的形式储存在一维数组中，如果该二叉树满足父节点小于等于子节点，叫做小堆；如果该二叉树满足父节点大于等于子节点，叫做大堆。
堆的实现
堆类型的创建
堆的物理结构本质上是顺序存储的，是线性的。但在逻辑上不是线性的，是完全二叉树的这种逻辑储存结构。 堆的这个数据结构，里面的成员包括一维数组，数组的容量，数组元素的个数。
代码语言：javascript复制ctypedef int HPDataType;
typedef struct heap
{
HPDataType* arr;
int size;
int capacity;
}Heap;堆的初始化
代码语言：javascript复制cvoid HeapInit(Heap* hp)
{
assert(hp);
hp->arr = NULL;
hp->size = hp->capacity = 0;
}堆的向上调整算法和向下调整算法
向上调整算法
给我的节点当做子节点，然后找到父节点，比较父子的大小，（看你是想建小堆还是大堆），直到比到子节点到根节点就停止比较，这时就已经调整好一次了。 下面的这个例子调整成的是小堆
代码语言：javascript复制cvoid swap(HPDataType* a, HPDataType* b)
{
HPDataType c = *a;
*a = *b;
*b = c;
}
void adjustup(Heap* hp, int child)
{
int father = (child - 1) / 2;
while (child > 0)
{
if (hp->arr[child] < hp->arr[father])
{
swap(&(hp->arr[child]), &(hp->arr[father]));
child = father;
father = (child - 1) / 2;
}
else
break;
}
}向下调整算法
给我的节点当做父节点，然后找到子节点(这个节点为左孩子，我们需要找到这两个孩子中较大的或者较小的当作子节点)，比较父子的大小，（看你是想建小堆还是大堆），直到比到子节点超过节点个数的时候就停止比较，这时就已经调整好一次了。
代码语言：javascript复制cvoid adjustdown(Heap* hp, int father)
{
int child = 2 * father 1;
while (child < hp->size)
{
//因为这里有child 1，所以要注意边界问题
if (child < hp->size-1&&hp->arr[child] > hp->arr[child 1])
child ;
if (hp->arr[child] < hp->arr[father])
{
swap(&(hp->arr[child]), &(hp->arr[father]));
father=child;
child = 2 * father 1;
}
else
break;
}
}堆的插入
为了不破坏堆的性质，我们在堆的最后进行插入(想一下其实在最后进行插入就不需要调整其他的元素了) 插入完成之后，我们需要调整成堆的形式。这里我们用堆的向上调整算法。进行调整.
代码语言：javascript复制cvoid HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
if (hp->size == hp->capacity)
{
int newcapcity = hp->capacity == 0 ? 4 : hp->capacity * 2;
HPDataType* newarr = (HPDataType*)realloc(hp->arr, newcapcity * sizeof(HPDateType));
if (newarr == NULL)
exit(-1);
hp->arr = newarr;
hp->capacity = newcapcity;
}
hp->arr[hp->size] = x;
hp->size ;
//向上调整
adjustup(hp,hp->size-1);
}堆的删除
对于删除堆头的数据，我们是把堆尾的数据覆盖头，元素个数减1，然后用堆的向下调整算法，进一步调整成堆。
代码语言：javascript复制cvoid HeapPop(Heap* hp)
{
assert(hp);
assert(hp->size);
swap(&(hp->arr[0]), &(hp->arr[hp->size-1]));
hp->size--;
//向下调整
adjustdown(hp,0);
}堆的销毁
代码语言：javascript复制cvoid HeapDestrop(Heap* hp)
{
assert(hp);
free(hp->arr);
hp->size = hp->capacity = 0;
}打印堆
代码语言：javascript复制cvoid HeapPrint(Heap* hp)
{
assert(hp);
for (int i = 0; i < hp->size; i )
{
printf("%d ", hp->arr[i]);
}
printf("n");
}给我一组数据，如果对他进行堆排序，那么前提就需要把它变成一个堆的形式
创建成堆
升序——建大堆 堆顶一定是最大的，那么我们每一次把堆顶的元素和堆尾的数据进行交换，那么最后一个元素为最大的元素，最后再次调整成堆的形式，这样依次可以得到次大的，最后的最后得到一个升序的数组。
降序——建小堆 堆顶一定是最小的，那么我们每一次把堆顶的元素和堆尾的数据进行交换，那么最后一个元素为最小的元素，最后再次调整成堆的形式，这样依次可以得到次小的，最后的最后得到一个降序的数组。
以降序为例
向上调整建堆
代码语言：javascript复制cvoid adjustdown(HPDataType* a,int n, int father)
{
int child = 2 * father 1;
if (child < n - 1&&a[child 1] < a[child])
child ;
if (child > n - 1 || a[father] <= a[child])
return;
swap(&a[child], &a[father]);
adjustdown(a, n, child);
}c int i = 0;
for (i = (n - 1 - 1) / 2; i >= 0; i--)
{
adjustdown(a,n, i);
}时间复杂度分析
给我父节点找子节点 设该二叉树的高度为h。 向上调整建堆，是从完全二叉树的倒数第二层开始。 第h-1层，每一个节点都要调整1次。——共调整2h-2
时间复杂度O(N)
向下调整建堆
代码语言：javascript复制cvoid adjustup(HPDataType* a, int child)
{
int father = (child - 1) / 2;
if (child <= 0 || a[father] <= a[child])
return;
swap(&a[child], &a[father]);
adjustup(a, father);
}c int i = 0;
for (i = 1; i <n; i )
{
adjustup(a, i);
}时间复杂度分析
给我子节点找父节点 我们从完全二叉树的第2层开始调整建堆。 具体的实现看下面的这张图
**时间复杂度O(N_logN)_
堆排序
时间复杂度O(NlogN)**
代码语言：javascript复制cvoid HeapSort(int* a, int n)
{
//建小堆
//向上建堆O(N)
int i = 0;
//for (i = (n - 1 - 1) / 2; i >= 0; i--)
//{
// adjustdown(a,n, i);
//}
//向下建堆O(N*logN)
for (i = 1; i <n; i )
{
adjustup(a, i);
}
//排序O(N*logN)
for (i = 0; i < n; i )
{
swap(&a[0], &a[n - 1 - i]);
adjustdown(a, n-i-1, 0);
}
}top-k问题
就是获取数据中前k个最大或者最小的数据
首先我们先建个一个k个数的堆，剩下的数据依次与堆顶的数据进行比较。 比如：我们要获取前k个最大的数据，首先建一个k个数的小堆，如果剩下的数据比堆顶的数据大，那么就进行交换。最后就得出前k个最大的数据。
节省空间
代码语言：javascript复制cvoid TopK(int* a, int n, int k)
{
//建堆
int* TopKHeap = (int*)malloc(sizeof(int) * k);
assert(TopKHeap);
for (int i = 0; i < k; i )
{
TopKHeap[i] = a[i];
}
for (int i =(k-1-1)/2; i >= 0; i--)
{
adjustdown(TopKHeap, k, i);
}
//获得前k个
for (int i = k; i < n; i )
{
if (TopKHeap[0] < a[i])
{
TopKHeap[0] = a[i];
adjustdown(TopKHeap, k, 0);
}
}
}时间复杂度O(k (N-k)logk)
