- 1. 堆的概念和结构
- 2. 堆向下调整法
- 3. 堆向上调整法
- 4. 堆的创建
- 5. 堆的插入
- 6. 堆的删除
- 7. 堆的数据个数
- 8. 取堆顶的数据
- 9. 堆的销毁
- 0.完整代码
堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
- 堆中某个节点的值总是不大于（大堆）或不小于（小堆）其父节点的值；2.堆总是一棵完全二叉树。
一般情况下，堆的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中。
typedef struct Heap {
HPDataType* _a;//指向数组的指针
int _size;//表示堆中元素个数
int _capacity;//表示堆的容量
}Heap;
例：大堆
小堆：
堆向下调整法的前提:根的左子树和右子树必须是一个堆
给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。
int array[] = {27,15,19,18,28,34,65,49,25,37};
我们先用图解的方法理解具体的实现步骤：
第一步：找到子节点中较小的结点并交换
第二步：将交换过的子节点当做根结点，重复第一步
第三步：将交换过的子节点当做根结点，重复第一步
第五步：将交换过的子节点当做根结点，重复第一步
发现其没有子节点，堆调整完成。
我们发现，堆的向下调整本质是一个循环，只要我们找到这个循环结束的条件，就很容易完成代码。
堆向下调整循环条件结束的标志就是子节点的下标大于存储堆的数组中元素个数的大小
由于多次用到交换，可以写一个函数封装起来
void Swap(HPDataType* a, HPDataType* b){
HPDataType temp = *a;
*a = *b;
*b = temp;
}
代码实现：
void AdjustDown(Heap* hp, int parent){
int child = parent * 2 + 1;//左子节点的下标为双亲节点*2+1
int size = hp->_size;//堆中元素的个数
while (child_a[child + 1] > hp->_a[child]){
child += 1;
}//如果左子节点不存在或者右子节点更小，将child移动到右子节点
if (hp->_a[parent] > hp->_a[child]){
Swap(&hp->_a[child], &hp->_a[parent]);
parent = child;
child = parent * 2 + 1;
}//如果双亲节点大于子节点，交换节点值并将子节点作为新的双亲节点进入循环
else{
return;
}
}
}
3. 堆向上调整法
堆向上调整法前提：除了最后一个叶子结点，其他结点符合堆的结构
我们在这个数组末尾加上10
int array[] = {15,18,19,25,28,34,65,49,27,37}
我们画图理解一下具体过程
找到子节点的双亲->比较大小->判断是否交换->找到新的双亲->比较大小->判断是否交换
也是一个递归的过程
堆向上调整的递归出口为双亲节点的下标小于0；
不难发现，由于在加入10的时候此二叉树已经符合堆的条件，所有我们只需要递归的和双亲节点对比交换即可。
实现代码：
void AdjustUp(Heap* hp){
int child = hp->_size - 1;
int parent = (child - 1) / 2;
while (child > 0){
if (hp->_a[parent] > hp->_a[child]){
Swap(&hp->_a[child], &hp->_a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else{
return;
}
}
}
4. 堆的创建
我们学会了如何调整一个只有根节点不符合堆特性的“堆”，那么如何能将随机数值的数组建成一个堆呢？
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？
int a[] = {1,5,3,8,7,6};
没错，我们可以从下往上来调整，这样保证调整该结点过后，该结点上面的结点都符合我们的堆向上调整法，便可将一个完全二叉树建成堆。
如何找到第一个非叶子结点呢，这里我们给出一个公式
在一个完全二叉树中，第一个非叶子结点在数组中的下标为：（size-2)/2
size为数组中元素个数
我们看看步骤：
我们发现当第三步完成后，其子树形成的堆结构被破坏
因此，在每一次交换的时候，都需要递归性的重新构造其子树
构建堆的代码如下：
void _HeapCreate(Heap* hp, HPDataType* a, int size){
hp->_a = (HPDataType*)malloc(sizeof(HPDataType)*size);
if (hp->_a == NULL)
{
assert(0);
return;
}
hp->_capacity = size;
hp->_size = 0;
memcpy(hp->_a, a, size*sizeof(HPDataType));
hp->_size = size;
for (int root = (size - 2) / 2; root >= 0; root--)
{
AdjustDown(hp, root);
}
}
补充：堆建立的时间复杂度为O（n）
堆插入的过程其实就是堆向上调整的过程，不过我们要对堆的结构进行更加细节的处理
我们在进行堆插入的时候要对堆空间进行判断，即判断堆结构里_size和_capacity的大小关系，如果小于，则正常加入，如果等于，便要扩容，以方便加入下一个元素，因为我们在每次等于的时候都会扩容，因此不会出现大于的情况。
实现扩容;
void CheakCapacity(Heap* hp){
assert(hp);
int newCapacity = hp->_capacity * 2;//新大小是原来的二倍
if (hp->_size == hp->_capacity){
int* newa = (HPDataType*)malloc(sizeof(HPDataType)*newCapacity);
for (int i = 0; i < hp->_size; i++){
newa[i] = hp->_a[i];
}
free(hp->_a);
hp->_a = newa;
hp->_capacity = newCapacity;
}
}
这样我们可以继续实现堆的插入：
void HeapPush(Heap* hp, HPDataType x){
CheakCapacity(hp);//调用容量判断
hp->_a[hp->_size] = x;
hp->_size++;
AdjustUp(hp);//调用堆向上调整
}
6. 堆的删除
对于堆的删除，我们一般默认删除堆顶元素。
将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，由于调整之后只有根节点不再满足堆的结果，我们再进行向下调整算法，得到一个新的堆，便完成对一个堆的删除。
我们来看看具体过程：
第一步：交换堆顶与最后一个元素
第二步：删除最后一个元素
第三步：使用堆向下调整法调整，得到新的堆
实现代码:
void HeapPop(Heap* hp){
if (HeapEmpty(hp)){
return;
}
Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
hp->_size -= 1;
AdjustDown(hp, 0);
}
7. 堆的数据个数
容易理解直接上代码了
int _HeapSize(Heap* hp){
assert(hp);
return hp->_size;
}
8. 取堆顶的数据
也简单，不过不能取空堆的数据，我们要考虑堆不能为空
判断堆是否为空：
int HeapEmpty(Heap* hp){
assert(hp);
return 0 == hp->_size;
}
实现：
HPDataType HeapTop(Heap* hp){
assert(!HeapEmpty(hp));
return hp->_a[0];
}
9. 堆的销毁
作为一个合格的程序员，当然不能忘记申请的空间是要还的~~
实现：
void HeapDestory(Heap* hp){
assert(hp);
if (hp->_a){
free(hp->_a);
hp->_a = NULL;
hp->_capacity = 0;
hp->_size = 0;
}
}
0.完整代码
heap.h
#include#include #include #include typedef int HPDataType; typedef struct Heap { HPDataType* _a; int _size; int _capacity; }Heap; //堆向上调整 void AdjustUp(Heap* hp); //堆向下调整 void AdjustDown(Heap* hp, int parent); // 堆的构建 void _HeapCreate(Heap* hp, HPDataType* a, int size); // 堆的销毁 void HeapDestory(Heap* hp); // 堆的插入 void HeapPush(Heap* hp, HPDataType x); // 堆的删除 void HeapPop(Heap* hp); // 取堆顶的数据 HPDataType HeapTop(Heap* hp); // 堆的数据个数 int _HeapSize(Heap* hp); // 堆的判空 int HeapEmpty(Heap* hp);
heap.c
#include"Heap.h"
void Swap(HPDataType* a, HPDataType* b){
HPDataType temp = *a;
*a = *b;
*b = temp;
}
//堆向下调整
void AdjustDown(Heap* hp, int parent){
int child = parent * 2 + 1;
int size = hp->_size;
while (child_a[child + 1] _a[child]){
child += 1;
}
if (hp->_a[parent] > hp->_a[child]){
Swap(&hp->_a[child], &hp->_a[parent]);
parent = child;
child = parent * 2 + 1;
}
else{
return;
}
}
}
void AdjustUp(Heap* hp){
int child = hp->_size - 1;
int parent = (child - 1) / 2;
while (child > 0){
if (hp->_a[parent] > hp->_a[child]){
Swap(&hp->_a[child], &hp->_a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else{
return;
}
}
}
//堆满扩容
static void CheakCapacity(Heap* hp){
assert(hp);
int newCapacity = hp->_capacity * 2;
if (hp->_size == hp->_capacity){
int* newa = (HPDataType*)malloc(sizeof(HPDataType)*newCapacity);
for (int i = 0; i < hp->_size; i++){
newa[i] = hp->_a[i];
}
free(hp->_a);
hp->_a = newa;
hp->_capacity = newCapacity;
}
}
// 堆的构建
void _HeapCreate(Heap* hp, HPDataType* a, int size){
hp->_a = (HPDataType*)malloc(sizeof(HPDataType)*size);
if (hp->_a == NULL)
{
assert(0);
return;
}
hp->_capacity = size;
hp->_size = 0;
memcpy(hp->_a, a, size*sizeof(HPDataType));
hp->_size = size;
for (int root = (size - 2) / 2; root >= 0; root--)
{
AdjustDown(hp, root);
}
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp){
assert(!HeapEmpty(hp));
return hp->_a[0];
}
// 堆的判空
int HeapEmpty(Heap* hp){
assert(hp);
return 0 == hp->_size;
}
//堆的数据个数
int _HeapSize(Heap* hp){
assert(hp);
return hp->_size;
}
// 堆的销毁
void HeapDestory(Heap* hp){
assert(hp);
if (hp->_a){
free(hp->_a);
hp->_a = NULL;
hp->_capacity = 0;
hp->_size = 0;
}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x){
CheakCapacity(hp);
hp->_a[hp->_size] = x;
hp->_size++;
AdjustUp(hp);
}
// 堆的删除
void HeapPop(Heap* hp){
if (HeapEmpty(hp)){
return;
}
Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
hp->_size -= 1;
AdjustDown(hp, 0);
}
还有自测的代码（可以忽略）
test(){
Heap hp;
int a[10] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
//AdjustDown(&hp, 0);
_HeapCreate(&hp, a, sizeof(a) / sizeof(a[0]));
printf("%d, %dn", _HeapSize(&hp), HeapTop(&hp));
HeapPush(&hp, 0);
printf("%d, %dn", _HeapSize(&hp), HeapTop(&hp));
printf("%dn", HeapTop(&hp));
HeapPop(&hp);
printf("%d, %dn", _HeapSize(&hp), HeapTop(&hp));
}
int main(){
test();
system("pause");
return 0;
}
