最小堆的实现

介绍

堆是一种数据结构，是一棵完整的二叉树。最小堆在堆的基础上增加了新的规则。其根节点的值最小，其任一节点的父节点的值小于或等于其左右节点的值。

密码

把堆想象成一棵树的数组对象。与任何节点相比，它满足以下三个特征。如果它有左右节点和一个父节点，则左节点的位置是i*2，右节点的位置是i*2 +1，父节点的位置是i/2。

堆的特性

用最小堆定义一个模板类min_stack。默认情况下，其初始大小为DEFAULT_SIZE=1024。c++中的容器向量用于缓存堆元素，length_表示堆的长度。

最小堆的模板类定义

insert方法将一段数据插入堆中。在插入时，它首先确定当前堆长度是否等于默认长度，如果是，它将容器的容量加倍。然后将数据插入数组的最后一位，根据堆的特点使用heap _ decrypt _ key方法将其移动到正确的位置。

最小堆插入数据

heap _ degrade _ key方法是用T值代替I的原值，然后根据堆的特点将其移动到正确的位置。移动过程是递归地将其与其父节点进行比较。如果它小于父节点，它的值将与父节点交换。如果它大于父节点，递归将结束，当前I值将是它的位置。

最小堆替换某结点值

Min_visitor获取最小堆的最小值，即返回其根节点的值，因为其根节点就是其最小值。

最小堆获取最小值

Min_pop返回最小堆的最小值，并删除最小值。删除后需要重新计算当前堆的最小值，因为删除最小值破坏了堆的特性。我们把数组的最后一个元素放在堆的根节点，堆的长度减1，然后用min_heapify方法求这个节点的最小堆。

最小堆获取最小值并删除它

min_heapify方法是为某个节点寻找最小堆的过程:首先计算当前节点的左右节点，将左右节点的值与当前节点的值进行比较，计算出其中最小节点的值。如果当前节点的值不是最小的，则将最小节点的值与当前节点的值交换，然后递归判断交换后的值及其左右节点的值。如果当前节点的值最小，则递归结束。

对某结点进行求最小堆的过程

Build_min_heap是一个构建堆的过程。只需要调用0-length/2的min_heapify方法就可以找到最小堆。因为length/2之后的所有子代都会经历寻找最小堆的过程，所以你只需要找到0-length/2的最小堆。

对整个数组进行建堆过程

Heap_sort堆排序是基于堆的，所以我们要先建一个堆，然后再排序。排序过程:每次将当前最小节点与数组末尾的节点值交换，交换完成后将堆的长度减1，然后对堆的根节点进行一次寻找最小堆的过程，找到另一个最小堆后，重复前面的动作，直到整个堆排序完成。这样一个排序后的数组就出来了，通过打印功能可以输出整个数组。

对整个数组进行堆排序过程

最小堆代码的测试用例:

最小堆的使用，代码实例

摘要

有两种堆，最小堆和最大堆。其实最大堆和最小堆的实现基本是一样的。最小堆的根是最小值，而最大堆的根是最大值。在某些判断中，当符号改变时，最小的堆就是最大的堆。最小堆有很多功能，比如排序，比如事件驱动。例如，当服务器判断套接字是否超时时，它会将最后一次通信时间存储在最小堆中。如果最小值和当前时间之间的时间差大于某个值，套接字将超时。需要了解很多编程和算法问题，请关注我，谢谢。