堆的认识
首先需要说明一点的问题是，这里我们所说的堆和使用malloc开辟的内存空间的那个堆，是完全不一样的，使用malloc的哪个堆，相当于是一块内存空间，而我们这里所说的堆，其实是一种数据结构，也是二叉树顺序存储最明显的一个例子
堆的概念及结构
如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质
堆中某个节点的值总是不大于或不小于其父节点的值；堆总是一棵完全二叉树堆顶元素一定是最大的或者最小的
举例
上面的结构，已经是一个小堆的结构了，但是，我们现在修改一下堆顶的元素，把堆顶的元素修改成100(如下所示)，然后现在看的话，这个树型的结构就既不是大堆也不是小堆了，因为堆顶的结点不满足小堆的性质 如果我们还希望把其当作堆来处理的话，那么我们就需要对上面的树型结构进行调整。我们需要将100进行向下调整，调整到一个什么情况呢，我们需要将100调整到属于他的位置，从而上面树型结构可以看成是一个堆的结构那么就需要将100进行向下调整，那么理所当然的，100的孩子就需要向上进行调整，在100的孩子里面选择一个较小的孩子，进行向上调整 上面的只是一个大致的调整过程，里面其实还是存在有一些问题的，我们会继续向下探究
堆向下调整的时间复杂度是多少？-
堆向下调整的时间复杂度是O(logn),因为从上到下移动的其实就是一棵树的高度(最差的情况下)，所以，其实就相当于是在求树的高度
再举一个例子
上面的哪个例子，之所以可以非常顺利的完成交换从而成为堆结构，是因为他的左子树和右子树，其实都已经是小堆的结构了，而上面这个例子的这棵树，他其实不能像上面的那个例子经过简单的交换就成为堆结构的，因为他的左右子树都不满足成为堆的结构，即使交换使得一边成为真正的堆结构，但是另一边，仍然不是堆的结构，向下调整parent的时候，必须保证parent的左右孩子是堆的结构，比如说，如果想要动8的话，那么需要先对他的子树进行调整。那么，现在来看一下，真正的建堆过程到底是什么样子的。得出的结论就是，如果你在调整一个树型结构的东西的话，其实是不能从堆顶元素开始调整的，应该从最后一个双亲结点开始调整，这样子的话，就可以确保每一个结点都被访问到，都被调整的，这样子的话，最终才会形成一个大堆或者说是一个小堆。所以说，上面的那一棵树，其实应该是需要从5那个结点开始进行调整的(从倒数第一个非叶子节点开始调整)
有关堆操作的代码
初级版本
Heap.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
typedef int HDataType
;
typedef struct Heap
{
HDataType
* array
;
int capacity
;
int size
;
}Heap
;
void HeapInit(Heap
* hp
,int init
);
void HeapCreate(Heap
* hp
, int* array
, int size
);
void HeapPush(Heap
* hp
, HDataType data
);
void HeapPop(Heap
* hp
);
HDataType
HeapTop(Heap
* hp
);
int HeapEmpty(Heap
* hp
);
int HeapSize(Heap
* hp
);
void HeapDestroy(Heap
* hp
);
void TestHeap();
Heap.c
#include"Heap.h"
void HeapInit(Heap
* hp
,int init
)
{
assert(hp
);
init
= init
< 10 ? 10 : init
;
hp
->array
= (HDataType
*)malloc(sizeof(HDataType
)* init
);
if (NULL == hp
->array
)
{
assert(0);
return;
}
hp
->size
= 0;
hp
->capacity
= init
;
}
void Swap(HDataType
* left
, HDataType
* right
)
{
HDataType temp
= *left
;
*left
= *right
;
*right
= temp
;
}
void AdjustDown(HDataType
* array
, int size
, int parent
)
{
int child
= parent
* 2 + 1;
while (child
< size
)
{
if (child
+1<size
&&array
[child
+ 1] < array
[child
])
{
child
+= 1;
}
if (array
[parent
] > array
[child
])
{
Swap(&array
[parent
], &array
[child
]);
parent
= child
;
child
= parent
* 2 + 1;
}
else
return;
}
}
void HeapCreate(Heap
* hp
, int* array
, int size
)
{
int root
= 0;
HeapInit(hp
, size
);
memcpy(hp
->array
, array
, sizeof(HDataType
) * size
);
hp
->size
= size
;
for (int root
= (size
- 2) / 2; root
>= 0; root
--)
{
AdjustDown(hp
->array
, hp
->size
, root
);
}
}
HDataType
HeapTop(Heap
* hp
)
{
assert(!HeapEmpty(hp
));
return hp
->array
[0];
}
int HeapEmpty(Heap
* hp
)
{
assert(hp
);
return 0 == hp
->size
;
}
int HeapSize(Heap
* hp
)
{
assert(hp
);
return hp
->size
;
}
void HeapPush(Heap
* hp
, HDataType data
);
void HeapPop(Heap
* hp
)
{
Swap(&hp
->array
[0], &hp
->array
[hp
->size
-1]);
hp
->size
--;
AdjustDown(hp
->array
, hp
->size
, 0);
}
void HeapDestroy(Heap
* hp
)
{
assert(hp
);
free(hp
->array
);
hp
->array
= NULL;
hp
->capacity
= 0;
hp
->size
= 0;
}
void TestHeap()
{
int array
[] = { 3,6,9,1,5,0,7,8,4,2 };
Heap hp
;
HeapCreate(&hp
, array
, sizeof(array
) / sizeof(array
[0]));
printf("heap size =%d\n", HeapSize(&hp
));
printf("heap top =%d\n",HeapTop(&hp
));
HeapPop(&hp
);
printf("heap size =%d\n", HeapSize(&hp
));
printf("heap top =%d\n", HeapTop(&hp
));
HeapDestroy(&hp
);
}
main.c
#include"Heap.h"
int main()
{
TestHeap();
return 0;
}
堆的插入
向上调整
堆的插入过程是需要进行向上调整的
问题1
我现在需要进行堆的插入，那么，当我需要插入这个元素的时候，那么这个元素很有可能会破坏原先已经存在的堆的性质，当然，他也有可能不会破坏原先堆已经有的性质，那么到底有没有破坏堆的性质呢？我们是需要用当前所插入的结点与其双亲结点进行比较的，那么我们为什么在进行插入操作的时候，不需要再两个结点中选择出一个较小的孩子呢？------原因在于，我们在进行插入一个元素之前，之前的完全二叉树的结构就已经是一个堆结构了，那么，其中的每一个结点都是满足堆特性的，所以说双亲结点一定比孩子结点大或者小，所以就不用将需要插入的结点和他的兄弟结点再进行比较了
问题2
我们之前实现的都是小堆，那么假设我现在需要去实现一个大堆，那么我要怎么办呢？----那我现在要去实现一个大堆的话，那么我的代码就需要去进行调整了，首先建堆的代码就是需要调整的，之前的建堆操作，建出来的堆时小堆，那么现在就需要让建出来的堆是一个大堆小堆是让小的元素尽量向上走，那么如果现在需要一个大堆的话，那么就需要让大的元素，尽量向上走，那么，就需要对向下调整的方法做出一定的调整，那么我就要去找两个孩子中较大的那一个孩子 但是问题又来了，如果我一会需要大堆，一会需要小堆的话，我就需要不停的去更改符号，那么这样的话，其实是非常麻烦的
问题3
堆的代码只给一份，要求这个代码既可以创建大堆，又可以创建小堆，需要大堆的时候创建大堆，需要小堆的时候创建小堆----在堆中的元素进行比较时，元素的操作就不可以写，也就是说让用户在外部来控制比较的方式—利用函数指针的方式来完成这个操作
Heap.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
typedef int HPDataType
;
typedef int (*CMP
)(HPDataType
, HPDataType
);
typedef struct Heap
{
HPDataType
* array
;
int size
;
int capacity
;
CMP Cmp
;
}Heap
;
int Less(HPDataType left
, HPDataType right
);
int Greater(HPDataType left
, HPDataType right
);
int (*Cmp
)(HPDataType left
, HPDataType right
);
void HeapInit(Heap
* hp
, int init
,CMP cmp
);
void HeapDestroy(Heap
* hp
);
void HeapCreate(Heap
* hp
, int* array
, int size
, CMP cmp
);
void HeapPush(Heap
* hp
, HPDataType data
);
void HeapPop(Heap
* hp
);
HPDataType
HeapTop(Heap
* hp
);
int HeapSize(Heap
* hp
);
int HeapEmpty(Heap
* hp
);
void TestHeap();
Heap.c
#include"Heap.h"
void HeapInit(Heap
* hp
, int init
, CMP cmp
)
{
assert(hp
);
init
= init
< 10 ? 10 : init
;
hp
->array
= (HPDataType
*)malloc(sizeof(HPDataType
) * init
);
if (NULL == hp
->array
)
{
assert(0);
return;
}
hp
->capacity
= init
;
hp
->size
= 0;
hp
->Cmp
= cmp
;
}
void Swap(HPDataType
* left
, HPDataType
* right
)
{
HPDataType temp
= *left
;
*left
= *right
;
*right
= temp
;
}
void AdjustDown(Heap
*hp
, int parent
)
{
int size
= hp
->size
;
int* array
= hp
->array
;
int child
= 2 * parent
+ 1;
while (child
< size
)
{
if (child
+1 < size
&& hp
->Cmp(array
[child
+ 1],array
[child
]))
{
child
+= 1;
}
if (hp
->Cmp(array
[child
],array
[parent
]))
{
Swap(&array
[child
], &array
[parent
]);
parent
= child
;
child
= 2 * parent
+ 1;
}
else
return;
}
}
void HeapCreate(Heap
* hp
, int* array
, int size
,CMP cmp
)
{
assert(hp
);
HeapInit(hp
, size
,cmp
);
memcpy(hp
->array
, array
, sizeof(HPDataType
) * size
);
hp
->size
= size
;
for (int root
= (size
- 2) / 2; root
>= 0; --root
)
{
AdjustDown(hp
, root
);
}
}
void HeapPop(Heap
* hp
)
{
assert(hp
);
Swap(&hp
->array
[0], &hp
->array
[hp
->size
- 1]);
hp
->size
--;
AdjustDown(hp
,0);
}
HPDataType
HeapTop(Heap
* hp
)
{
assert(hp
);
return hp
->array
[0];
}
int HeapSize(Heap
* hp
)
{
assert(hp
);
return hp
->size
;
}
int HeapEmpty(Heap
* hp
)
{
assert(hp
);
return 0 == hp
->size
;
}
void HeapDestroy(Heap
* hp
)
{
assert(hp
);
free(hp
->array
);
hp
->array
= NULL;
hp
->size
= 0;
hp
->capacity
= 0;
}
void AdjustUP(Heap
*hp
,int child
)
{
int parent
= (child
- 1) >> 1;
HPDataType
* array
= hp
->array
;
int size
= hp
->size
;
while (child
)
{
if (hp
->Cmp(array
[child
] , array
[parent
]))
{
Swap(&array
[child
], &array
[parent
]);
child
= parent
;
parent
= (child
- 1) >> 1;
}
else
return;
}
}
void CheckCapacity(Heap
* hp
)
{
assert(hp
);
if (hp
->size
== hp
->capacity
)
{
int newcapacity
= 2 * hp
->capacity
;
HPDataType
* temp
= (HPDataType
*)malloc(sizeof(HPDataType
) * newcapacity
);
if (NULL == temp
)
{
assert(0);
return;
}
for (int i
= 0; i
< hp
->size
; ++i
)
{
temp
[i
] = hp
->array
[i
];
}
free(hp
->array
);
hp
->array
= temp
;
hp
->capacity
= newcapacity
;
}
}
void HeapPush(Heap
* hp
, HPDataType data
)
{
CheckCapacity(hp
);
hp
->array
[hp
->size
] = data
;
hp
->size
++;
AdjustUp(hp
->array
, hp
->size
, hp
->size
- 1);
}
int Less(HPDataType left
, HPDataType right
)
{
return left
< right
;
}
int Greater(HPDataType left
, HPDataType right
)
{
return left
> right
;
}
void TestHeap()
{
int array
[] = { 3,6,9,1,5,0,7,8,4,2 };
Heap hp
;
HeapCreate(&hp
, array
, sizeof(array
) / sizeof(array
[0]),Less
);
printf("heap size =%d\n", HeapSize(&hp
));
printf("heap top =%d\n", HeapTop(&hp
));
HeapPop(&hp
);
printf("heap size =%d\n", HeapSize(&hp
));
printf("heap top =%d\n", HeapTop(&hp
));
HeapPush(&hp
,-1);
printf("heap size =%d\n", HeapSize(&hp
));
printf("heap top =%d\n", HeapTop(&hp
));
HeapDestroy(&hp
);
}
main.c
#include"Heap.h"
int main()
{
Cmp
= Less
;
Cmp(10, 20);
Cmp
= Greater
;
Cmp(10, 20);
TestHeap();
return 0;
}
堆的应用
堆的第一个应用：
TOP-K 问题
因为数据量太大了，不能一次加载到内存里面，所以说上面的排序的的方法是行不通的(因为有些排序的方法是可以解决Topk问题的—例如，归并排序就可以解决上面的问题，不过都是后话了)然后，其实第一种方法也是行不通的，因为数据量非常的庞大，一次一次去遍历，那么肯定是需要保存下来的，但是内存里面又是确实放不下的，时间太慢了
用堆来解决问题
时间复杂度的问题
用堆解决TopK问题的时间复杂度，如果要找前k个最大元素的话，那么一开始就用前k个元素去创建一个小堆，单次向下调整的复杂度为logn，但是在建堆的过程中，需要调用n次向下调整的方法，所以建堆的时间复杂度为klogk，这个时候，剩下n-k的元素，剩下的n-k个元素所采用的方法和之前的一样，所以，利用堆来解决TopK问题的时间复杂度如下所示:
堆的第二个应用：
堆排序
要使用堆来进行排序的话，首先我们需要先去建立一个堆升序建立大顶堆降序建立小顶堆
选择题
(1)--------------------选A (2)---------------------选C 删除掉堆顶元素之后如下所示 所以一共比较了3次 (3)------------------------选C (4)----------------------选C 调整之后的结果为：
