目录

一、堆到底是什么？

二、堆的分类总览

三、二叉堆—— 堆家族的爆款

3.1 二叉堆长什么样？

3.2 二叉堆怎么存储？

3.3 二叉堆的核心操作

3.3.1 插入（上滤 / Sift Up）-以大堆为例

3.3.2 删除堆顶（下滤 / Sift Down）

3.33 其他简单操作

3.34 gitee链接

读完这篇文章，你将彻底搞清楚：

• 堆到底是什么？

• 堆有哪些分类和变种？

• 如何用代码实现二叉堆的基本操作？

一、堆到底是什么？

首先，别把数据结构的“堆”和内存中的“堆空间”搞混了，这俩完全是两码事。

我们先来给它下个官方定义：

堆（Heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象，并满足堆序性：父节点的值总是大于或等于（或小于或等于）子节点的值。

看不懂？没关系，大白话解释：

想象你在排队买奶茶。

正常的队伍是“先来后到”，谁先来谁先买。但有时候，VIP可以插队，孕妇老人可以优先——这就是“优先级”的概念，本质上就是一个能够快速找到最大值或最小值的“优先级队列”。

再换个更形象的比喻：

堆就像一个公司组织架构图。

老板在最顶上，下面是各种副总裁，再下面是部门经理，再往下是普通员工。

在“大顶堆”的公司里，老板的工资最高，副总裁的工资比经理高，经理的工资比员工高——这就是“每个父节点的值都比子节点大”。

在“小顶堆”的公司里，老板的工资最低（好惨的老板），副总裁的工资比经理低——这就是“每个父节点的值都比子节点小”。

二、堆的分类总览

    这是堆家族 我这里只讲最简单的二叉家族 后面的大家会在后续的学习中慢慢了解到 再回来看我的补充文章 嘿嘿！！！

三、二叉堆—— 堆家族的爆款

一句话概括：二叉堆是堆家族里最常用、最简单的成员，是完全二叉树 + 堆序性的组合。

3.1 二叉堆长什么样？

二叉堆的逻辑结构是一棵完全二叉树（除了最后一层，其他层全部满员，且最后一层的叶子从左到右紧密排列）

二叉堆分为两种：

• 大顶堆（最大堆） ：父节点的值 ≥ 子节点的值，根节点是最大值

• 小顶堆（最小堆） ：父节点的值 ≤ 子节点的值，根节点是最小值

3.2 二叉堆怎么存储？

最妙的地方来了：二叉堆不用指针！只用数组就能存！

因为是完全二叉树，我们可以用层序遍历的顺序把节点放进数组里：

假设根节点在数组下标为 1 的位置（也可以从 0 开始），那么：
节点 i 的左孩子 = i × 2+1
节点 i 的右孩子 = i × 2+2
节点 i 的父节点 = （i-1）÷2

3.3 二叉堆的核心操作

二叉堆最核心的操作只有两个：插入（上滤） 和删除堆顶（下滤）。

3.3.1 插入（上滤 / Sift Up）-以大堆为例

1. 把新元素放到数组的最后面（相当于堆的最底层最右边）

2. 让它跟自己的父节点比大小

3. 如果它比父节点大（以大顶堆为例），就交换位置

4. 重复步骤2-3，直到它比父节点小，或者到了根节点为止

5. //堆的向上调整算法
   void AdjustUp(Datatype* arr, int child)
   {
   	int parent = (child - 1) / 2;
   	while (child > 0)//因为child这里是往上走的下标在变下
   	{
   		//这里我们先以大堆作为示例 小堆相反即可
   		if (arr[child] < arr[child + 1])//感觉这里有点小问题
   		{
   			child++;
   		}
   		if (arr[child] > arr[parent])
   		{
   			Swap(&arr[child], &arr[parent]);
   			child = parent;
   			parent = (child - 1) / 2;
   		}
   		else
   		{
   			break;
   		}
   	}
   }
   
   // 堆的插入--配合向上调整
   void HeapPush(Heap* hp, Datatype x)
   {
   	assert(hp);
   	if (hp->capacity == hp->size)
   	{
   		int Newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 4;
   		Datatype* tmp = (Datatype*)realloc(hp->arr, sizeof(Datatype) * Newcapacity);
   		if (tmp==NULL)
   		{
   			printf("内存分配失败!!\n");
   			exit(1);
   		}
   		hp->arr = tmp;
   		hp->capacity = Newcapacity;
   	}
   	hp->arr[hp->size] = x;
   	AdjustUp(hp->arr,hp->size);
   	hp->size++;
   }

这个过程就像新员工升职——只要有本事比上级强，就一直往上升，直到遇到更强的上级为止。

3.3.2 删除堆顶（下滤 / Sift Down）

1. 把最后一个元素放到堆顶位置（覆盖掉原来的堆顶）

2. 让它跟两个子节点中较大的那个比大小

3. 如果它比子节点小，就交换位置

4. 重复步骤2-3，直到它比子节点都大，或者到了叶子节点为止

5. //堆的向下调整算法
   void AdjustDown(Datatype* arr,int parent, int n)
   {
   	int child = parent * 2 + 1;
   	while (child < n)//因为child这里是往下走的下标在变大
   	{
   		if (child + 1 < n && arr[child] < arr[child + 1])//考虑到只有一个点的情况 加上child+1>0
   		{
   			child++;
   		}
   		if (arr[child] > arr[parent])
   		{
   			Swap(&arr[child], &arr[parent]);
   			parent = child;//这是从上往下调整所以是parent=child
   			child = parent * 2 + 1;
   		}
   		else
   		{
   			break;
   		}
   	}
   }
   // 堆的删除-----从堆顶开始删 然后恢复原来堆结构-配合向下调整
   void HeapPop(Heap* hp)
   {
   	assert(!EmptyHeap(hp));
   	Swap(&hp->arr[0], &hp->arr[hp->size - 1]);
   	hp->size--;
   	AdjustDown(hp->arr, 0, hp->size);
   }

这个过程就像CEO被开除后，从基层拉一个人临时顶上，然后不断被更优秀的员工PK下去，直到找到合适的位置。

3.33 其他简单操作

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

//打印堆
void PrintHeap(Heap* hp)
{
    assert(hp);
    int i = 0;
    while (i<hp->size)//有效数据是4 但是数组下标为3 这点不要在其他地方用错了
    {
        printf("%d ", hp->arr[i]);
        i++;
    }
    printf("\n");
}
//销毁堆
void HeapDestory(Heap* hp)
{
    assert(hp);
    if (hp->arr)
    {
        free(hp->arr);
        hp->arr = NULL;
    }
    hp->capacity = hp->size = 0;
    //free(hp); 这里的hp是栈上的不能被销毁 其他操作已经是完整的了 
    //free（）只能销毁malloc realloc calloc上分配的空间
    hp = NULL;
}
//堆的判空
bool EmptyHeap(Heap* hp)
{
    assert(hp);
    return hp->size == 0;
}

// 取堆顶的数据
Datatype HeapTop(Heap* hp)
{
    assert(hp);
    return hp->arr[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
    assert(hp);
    return hp->size;
}

3.34 gitee链接

如果你想看看基础操作的实现文件可以看看我的gitee链接里面有各种数据结构的简单操作实现

https://gitee.com/jiangmingpeng0716/learning-of-data-structures

不喜勿喷 学习中~~~~~