目录

1、堆的概念及结构

概念

规律 

2、堆的实现

2.1结构设计

2.2接口实现

2.3 初始化 

2.4堆的向下调整算法

主要思想

涉及问题

代码实现

2.5建堆

思想

代码实现

建堆的时间复杂度

2.6 堆的向上调整算法

主要思想

​涉及问题

代码实现

2.7 插入 

2.8删除堆顶元素

2.9取堆顶元素

2.10 堆的大小

2.11 堆是否为空

2.12 堆销毁

3、源代码

1. 头文件

2. 接口函数

3.测试文件

1、堆的概念及结构

概念

        堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

性质1：堆中某个结点的值总是不大于或不小于其父结点的值；
性质2：堆总是一棵完全二叉树。

        将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

        如下，小堆的父亲节点总是小于其孩子节点，所以小堆的根节点一定是最小的。而大堆的父亲节点总是大于其孩子节点，所以大堆的根节点一定是最大的。

规律 

        既然堆的逻辑结构是完全二叉树，那么它就同样具有完全二叉树的性质。

         对于完全二叉树，若从上至下、从左至右编号，以根节点为0开始，则编号为i的节点，其左孩子节点编号为2i+1，右孩子节点编号为2i+2，父亲节点为 (i-1) / 2。 这个规律非常重要！！！

         我们来验证一下：

        一棵节点个数为N的完全二叉树，其高度为 h = log 2 (N+1)   ，（2为底数）。

        推导过程如下：

        我们来做个简单的题目：

1.下列关键字序列为堆的是？（）

A 100,60 ,70 ,50 ,32 ,65
B 60 ,76 ,65 ,50 ,32 ,100
C 65 ,100,70 ,32 ,50 ,60
D 70 ,65 ,100,32 ,50 ,60
E 32 ,50 ,100,70 ,65 ,60
F 50 ,100, 70,65 ,60 ,32

        在这里，由于堆的存储结构是数组，且堆是完全二叉树，可以直接如下图A，把后面的移过去，每一层放置可以放的最大节点个数，直到数组内元素放置完。很容易就可以看出 A 是堆。

2、堆的实现

2.1结构设计

        如下，用数组存储数据，实际存储结构是数组。

typedef int HeapDataType;typedef struct Heap
{HeapDataType* a;int size; //已有数据个数int capacity; //容量
}HP;

2.2接口实现

2.3 初始化 

        如下，非常简单，就不多说了。

//初始化
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}

2.4堆的向下调整算法

主要思想

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

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

        我们可以通过画图构建这棵树，然后走一遍向下调整的过程，如下图 （a）是构建的完全二叉树，从（b）中明显看出，根节点的左右子树都是小堆，所以可以调整。而横线下方就是调整的详细步骤，每一次，根节点都和左右孩子节点中，较小的那个孩子交换 ：

涉及问题

        在此过程中，我们要明确几个问题：
1、如何找到孩子节点？

2、如何判断该孩子节点是否存在？（比如值为 28 的节点，不存在右孩子）

3、边界条件？什么时候停止调整？

        由于堆逻辑结构是一颗完全二叉树，所以要利用上面完全二叉树的规律。

        1、  我们用 parent、leftchild、rightchild，分别代表父亲节点、左右孩子节点的下标（物理结构是数组）。 根据规律得：  leftchild = parent * 2 + 1 ，rightchild = parent * 2 + 2 。并且任一节点 i ，其父亲节点 parent = (i-1)/2 。

        2、由于数组一共有n个元素，其下标最大是 n-1，所以孩子节点的下标只要 小于 n ，就是存在的。

        3、首先，由于其子树是小堆，所以如果调整到某个节点，其父亲节点比孩子节点都小，就不需要调整了，那么已经构建成功（相当于做了一半就成功）。

        其次，就是调整到最后一步的情况，如下。每次调整，改变的都是代表父亲节点和孩子节点 下标的那几个变量。父亲节点的值和孩子节点的值交换之后，下一轮调整 父亲节点的下标就变成了上一轮孩子节点的下标，孩子节点的下标变成当前 父亲节点的孩子节点中 小的那个的下标。所以孩子节点 > n，那么就代表调整到了最下面一层，不需要再调整了。

          小结论： 如上图，向下调整算法前提是，根节点的左右子树都是大堆或者都是小堆。然后调整之后的结果是，根节点调整到了下方，整棵树成了一个堆。    但是，我们深入思考一下，如果现在调整的根节点，也是某个节点的孩子节点呢？ 那么，就能得到，向下调整算法实际上是调整的某一个节点 A，要这个节点的左右子树都是同种堆，调整之后，以原 A 位置的节点为根节点的树是一个堆。

        如下，从左边标红的地方开始向下调整，不用管其父亲节点等，只需要知道标红节点的左右子树都是同种堆即可，然后调整得到右半边结果。（很重要，要理解！！！这是理解建堆算法的前提！！！）

代码实现

        如下，由于一次只需要交换一个父亲节点和一个孩子节点，且孩子节点存储时是相邻的，所以用child 先表示 左孩子节点下标，然后循环内部和右孩子节点比较，如果右孩子节点存在且其值小于左孩子节点的值，那么child++ ，++之后的child节点表示的是右孩子节点。 然后比较，需要交换就交换parent 和 child 代表的下标的内容，然后parent 和 child 更新；如果不需要交换，那么就是调整好的，break。

        传入三个参数，依次是指向堆的数据的指针，堆的长度，根节点。

void Swap(HeapDataType* a, HeapDataType* b)
{int c = *a;*a = *b;*b = c;
}//向下调整
void AdjustDown(HeapDataType* a, int n, int parent)
{assert(a);int child = parent * 2 + 1; // 这里和链表里的长链表、短链表有异曲同工之妙，只不过这里只需要用到大的孩子while (child a[child + 1] && child + 1 size ，不可以=，因为数据个数是比下标大1{child++;}if (a[parent] > a[child]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else // 父亲小于等于孩子，所以已经完成调整，直接break{break;}}
}

2.5建堆

思想

        建堆写在这里，相信聪明的你已经猜到，需要使用向下调整算法，要使用这个算法，就要有一个前提 —— 要调整的节点，左右子树都是同种堆。

        如下，方法一，我们从根节点开始调整，但是本身这棵树就是乱序的，没有哪一个节点的子树能保证是堆，更不要说是同种堆了。所以这种方法根本不可行。

        既然从一棵树的上方开始调整不行，那么我们就从下方开始调整，如方法二。但是这里开始调整的起始位置也很有讲究，是从最后一个节点开始吗？ 显然不是，从上面的小规律已经得知，向下调整算法实际上是调整了开始的那个节点，而一棵树最后一个节点是叶子节点，叶子节点根本没有孩子节点，更不要说子树了，没有什么好调整的。所以我们要从有孩子节点的 节点开始调整。

        如下方法2 ，从圈出来的步骤 1 到步骤5 。步骤一中，值为37 的节点，左右子树都是堆，可以调整这个值为37的节点。后面依次也是。最后完成调整，建队成功。

代码实现

        如下，传入三个参数，依次是堆指针，数组，数组长度。  首先把开辟堆内存储数据的空间，然后把数组的值复制进去，然后建堆。

void HeapCreat(HP* php, HeapDataType* a, int len)
{assert(php);assert(a);php->a = (HeapDataType*)malloc(sizeof(HeapDataType) * len);if (php->a == NULL){perror("malloc fail::");exit(-1);}memcpy(php->a, a, sizeof(HeapDataType) * len);php->size = php->capacity = len;for (int i = (len - 1 - 1) / 2;i >= 0;i--){AdjustDown(php->a, php->size, i);}}

建堆的时间复杂度

        由于建堆是从倒数第二行开始，所以 是 h-1 层开始计数。最终结果约等于 N 。所以向下调整算法建堆的时间复杂度是O（N）。

2.6 堆的向上调整算法

主要思想

        向上调整算法是从节点 n 开始，调整 节点n 到根节点 之间的路径上的节点（任一节点到根节点之间的路径唯一）。其结果是，将这条路径上，最大或者最小的节点，放到根节点位置。这个算法的前提是：这条路径，除了节点n，其余节点要满足堆的特性，即有序。（自己用文字总结的，可能存在一些不标准的地方，欢迎指正！）

        比如，现有一个数组，其逻辑结构是一个堆，新加一个元素再数组末尾，并且使用向上调整算法使其保持逻辑结构依然是一个堆。

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

新增 6 放在数组末尾。

          如下，不难看出，向上调整算法的路径是： 6 — 28 — 15 — 12 。而除了6 所代表的节点，这条路径上，从上往下看，是升序的，所以最后结果是，这条路径上的最小值到了根节点的位置。

涉及问题

         这里的问题无非和向下调整算法类似。找父亲节点也不难，最主要的就是边界条件，即如何确定循环结束条件。通过上面的图片可以看出， child = 0 就结束了，所以控制条件如下面代码所示。

代码实现

        如下，传入两个参数，一个是指向堆的数据的指针，一个是要调整的孩子节点。

void AdjustUp(HeapDataType* a, int child)
{assert(a);int parent = (child - 1) / 2;while (child > 0){if (a[parent] }

         此外，也可以通过向上调整算法建堆，当然了，用该算法，要从上面往下建堆，而不是从下往上。 从根节点到最后一个节点依次调整，这样就可以保证，每一条路径，除了n节点之前的节点，都是有序的。如下：

         核心代码如下，前面开辟空间和复制什么的，和向下调整建堆一摸一样，就不写了。

for (int i = 1;i {AdjustUp(a, i);
}

2.7 插入 

        由于存储结构是数组，所以插入要考虑是否扩容。

void HeapPush(HP* php, HeapDataType x)
{assert(php);//扩容if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HeapDataType* ptr = (HeapDataType*)realloc(php->a, sizeof(HeapDataType) * newcapacity);if (ptr == NULL){perror("realloc fali::");exit(-1);}php->a = ptr;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

2.8删除堆顶元素

        把堆尾元素放到堆顶元素，然后去除堆尾元素（这里直接size--），再向下调整即可。因为原本就是一个堆，现在堆顶元素变了，所以直接向下调整。

void HeapPop(HP* php)
{assert(php);assert(php->size > 0);php->a[0] = php->a[php->size - 1];php->size--;AdjustDown(php->a, php->size, 0);
}


2.9取堆顶元素

HeapDataType HeapTop(HP* php)
{assert(php);assert(!php->a);return php->a[0];
}

2.10 堆的大小

int HeapSize(HP* php)
{assert(php);return php->size;
}

2.11 堆是否为空

bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

2.12 堆销毁

//销毁
void HeapDestory(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}

3、源代码

1. 头文件

#pragma once
#include
#include
#include
#include
#include
#includetypedef int HeapDataType;typedef struct Heap
{HeapDataType* a;int size; //已有数据个数int capacity; //容量
}HP;//初始化
void HeapInit(HP* php);
//插入
void HeapPush(HP* php, HeapDataType x);
//删除堆顶元素
void HeapPop(HP* php);
//销毁
void HeapDestory(HP* php);
//向上调整
void AdjustUp(HeapDataType* a, int child);
void AdjustDown(HeapDataType* a, int n);
//建堆
void HeapCreat(HP* php, HeapDataType* a, int len);
//打印
void Print(HP* php);
//取堆顶元素
HeapDataType HeapTop(HP* php);
int HeapSize(HP* php);
bool HeapEmpty(HP* php);

2. 接口函数

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"//初始化
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}//插入
void HeapPush(HP* php, HeapDataType x)
{assert(php);//扩容if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HeapDataType* ptr = (HeapDataType*)realloc(php->a, sizeof(HeapDataType) * newcapacity);if (ptr == NULL){perror("realloc fali::");exit(-1);}php->a = ptr;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}//销毁
void HeapDestory(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}void Swap(HeapDataType* a, HeapDataType* b)
{int c = *a;*a = *b;*b = c;
}//向上调整
void AdjustUp(HeapDataType* a, int child)
{assert(a);int parent = (child - 1) / 2;while (child > 0){if (a[parent] }void Print(HP* php)
{for (int i = 0;i size;i++){printf("%d ", php->a[i]);}printf("\n");
}//向下调整
void AdjustDown(HeapDataType* a, int n, int parent)
{assert(a);int child = parent * 2 + 1; // 这里和链表里的长链表、短链表有异曲同工之妙，只不过这里只需要用到大的孩子while (child a[child + 1] && child + 1 size ，不可以=，因为数据个数是比下标大1{child++;}if (a[parent] > a[child]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapPop(HP* php)
{assert(php);assert(php->size > 0);php->a[0] = php->a[php->size - 1];php->size--;AdjustDown(php->a, php->size, 0);
}HeapDataType HeapTop(HP* php)
{assert(php);assert(!php->a);return php->a[0];
}void HeapCreat(HP* php, HeapDataType* a, int len)
{assert(php);assert(a);php->a = (HeapDataType*)malloc(sizeof(HeapDataType) * len);if (php->a == NULL){perror("malloc fail::");exit(-1);}memcpy(php->a, a, sizeof(HeapDataType) * len);php->size = php->capacity = len;for (int i = (len - 1 - 1) / 2;i >= 0;i--){AdjustDown(php->a, php->size, i);}}int HeapSize(HP* php)
{assert(php);return php->size;
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

3.测试文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"Test1()
{int arr[] = { 10,78,99,45,67,45,0,77,34 };HP hp;HeapInit(&hp);for (int i = 0;i }Test2()
{int arr[] = { 10,78,99,45,67,45,0,77,34 };HP hp;HeapInit(&hp);HeapCreat(&hp, arr, sizeof(arr) / sizeof(arr[0]));Print(&hp);
}int main()
{//Test1();//Test2();return 0;
}