网站流量是怎么计算的,杭州省建设厅网站,过控专业简历制作,电商联盟推广STL —heap算法源码刨析 heap算法概述push_heap 插入元素pop_heap 取出根节点元素sort_heap 按极值存放元素make_heap 将一段现有数据构造成heap程序测试 heap算法概述
heap的内部是一个完全二叉树#xff0c;将极值存放在根节点。这个里的极值可分为最大值、最小值。根据极值… STL —heap算法源码刨析 heap算法概述push_heap 插入元素pop_heap 取出根节点元素sort_heap 按极值存放元素make_heap 将一段现有数据构造成heap程序测试 heap算法概述
heap的内部是一个完全二叉树将极值存放在根节点。这个里的极值可分为最大值、最小值。根据极值意义的不同可分为大堆和小堆。为了方便解释以下的讲解内容都以大堆max-heap的例子讲解。 大顶堆 根节点堆顶元素是所有节点中的最大值父节点都大于左右子节点。 小顶堆 小顶堆中的根节点是所有节点中的最小值父节点都小于左右子节点。 如上图所示A即为这个列表中的极值。在查找极值时极为方便。同时因为是一个完全二叉树所以除了叶子节点外其他的节点都存在。因此可以通过索引值来找到父节点和左右子节点之间的关系。当父节点索引值为i时左子节点索引值2i1,右子节点索引值为2i2。 具体原理可查看此博客堆排序中 i 位置的节点的子节点位置为 2i1, 2i2, 父节点为 (i-1) / 2
push_heap 插入元素 数据插入示意图 将要插入的元素放入容器的尾端。通过调用push_heap()函数将尾端的元素放入到完全二叉树的合适位置。
//计算元素之间的距离
templateclass ForwardIterator
typename std::iterator_traitsForwardIterator::difference_type Distance(ForwardIterator first, ForwardIterator last)
{typename std::iterator_traitsForwardIterator::difference_type n 0;while (first ! last){first;n;}return n;
}//获取元素类型
templateclass Iterator
inline typename std::iterator_traitsIterator::value_type* value_Type(const Iterator)
{return static_caststd::iterator_traitsIterator::value_type * (0);
}//获取表示距离的类型
templateclass Iterator
inline typename std::iterator_traitsIterator::difference_type* distance_type(const Iterator)
{return static_caststd::iterator_traitsIterator::difference_type * (0);
}
templateclass RandomAcessIterator, class Distance, class T
void _push_heap(RandomAcessIterator first, Distance holeIndex, Distance topIndex, T value)
{Distance parent (holeIndex - 1) / 2; //找到父节点while (holeIndex topIndex *(first parent) value) //当索引值不为根节点时或者父节点小于插入空节点时{*(first holeIndex) *(first parent);//父节点的值复制给空节点holeIndex parent; //父节点索引值复制给空节点parent (holeIndex-1) / 2; //查找此时空节点的父节点}*(first holeIndex) value; //将值复制到此时的空节点上
}templateclass RandomAcessIterator, class Distance, class T
inline void _push_heap_aux(RandomAcessIterator first, RandomAcessIterator last, Distance*, T*)
{int count last - first;_push_heap(first, Distance((last - first) - 1), Distance(0), T(*(last - 1)));
}template class RandomAcessIterator
inline void USD_push_heap(RandomAcessIterator first, RandomAcessIterator last)
{_push_heap_aux(first, last, distance_type(first), value_Type(first));
}这是是一个插入操作将数据写入到字符串的尾端。找到尾端所对应的父节点进行对比。如果大于父节点两个节点对调。找到根节点或者插入空节点小于父节点时循环操作结束。此时插入的值被放入合适的位置。元素的插入可参考示意图的操作。 pop_heap 取出根节点元素
调用 函数pop_heap(),会将根节点的值取出来存在放在容器的尾端。同时会按照完全二叉树的规则重新移动剩余的元素找出剩余元素中的极值存放在根节点中构建出一个新的完全二叉树。此时要取出的元素位于尾部再通过容器自身的操作取出尾部的元素。 元素取出示意图
templateclass RandomAcessIterator, class Distance, class T
void _adjust_heap(RandomAcessIterator first, Distance holeIndex, Distance len, T value)
{Distance topIndex holeIndex; //根节点Distance sencondChild 2 * holeIndex 2; //右子节点while (sencondChild len){if (*(first sencondChild) *(first sencondChild - 1)) //右子节点与左子节点进行比较{sencondChild--; //通过移动找到左子节点}*(first holeIndex) *(first sencondChild);//将较大的值复制给空值元素所在的位置holeIndex sencondChild; //空值元素移动到较大值元素位置上sencondChild 2 * sencondChild 2; //再次查找对应的右子节点}if (sencondChild len) //此时右子节点等于树的长度那么右子树不存在将左子树元素复制给空值元素{*(first holeIndex) *(first sencondChild-1);holeIndex sencondChild-1;}_push_heap(first, holeIndex, topIndex,value);//将原二叉树的尾部元素插入到现在空值元素位置上
}templateclass RandomAcessIterator,class T,class Distance
inline void _pop_heap(RandomAcessIterator first, RandomAcessIterator last, RandomAcessIterator result,T value,Distance *)
{*result *first;_adjust_heap(first, Distance(0), Distance(last - first), value);
}templateclass RandomAcessIterator,class T
inline void _pop_heap_aux(RandomAcessIterator first, RandomAcessIterator last,T*)
{_pop_heap(first, last-1, last - 1, T(*(last - 1)), distance_type(first));
}templateclass RandomAcessIterator
inline void USD_pop_heap(RandomAcessIterator first, RandomAcessIterator last)
{_pop_heap_aux(first,last,value_Type(first));
}此算法中的核心逻辑调用_adjust_heap()首先holeIndex 0此时空值元素代表的是根节点找到根节点对应的右子节点根节点的右子节点和左子节点进行相比。空值元素与相比后较大值元素进行对换此时较大值元素就作为了根节点同时空值元素移动到了较大值的位置。重复上述操作在继续查找控制元素的右子节点与它的左子节点进行对比。只到所查值的右子节点索引值大于树的长长度。则停止查找。查找结束后将原完全二叉树的尾节点复制到空值所在的位置。操作流程可参考此函数的示意图。 sort_heap 按极值存放元素
将元素按照极值从尾到前开始存放元素
templateclass RandomAcessIterator
void USD_sort_heap(RandomAcessIterator first, RandomAcessIterator last)
{while (last - first1){USD_pop_heap(first,last--);}
}通过使用pop_heap()操作将结果存放在尾部同时缩短last的索引值。这样每pop_heap一次就会构造一个新的二叉树同时尾部会存放上一个二叉树的根节点。 make_heap 将一段现有数据构造成heap
容器中存放一段数据通过make操作后会更改容器中元素的位置。从而满足 堆的要求。
templateclass RandomAcessIterator,class T,class Distance
void _make_heap(RandomAcessIterator first, RandomAcessIterator last, T*, Distance*)
{if (last - first2){return;}Distance len last - first;Distance parent (len - 2) / 2; //最后一个父节点while (true){_adjust_heap(first, parent, len, *(first parent));if (parent 0){return;}parent--;}
}templateclass RandomAcessIterator
inline void USD_make_heap(RandomAcessIterator first, RandomAcessIterator last)
{_make_heap( first,last, value_Type(first), distance_type(first));
}此算法的思路首先找到最后一个父节点。通过调用_adjust_heap()函数来调整此时的父节点和左右两个子节点之间的关系。来满足heap的条件。当此节点和其子节点调整结束后通过移动parent索引值找到下一个父节点再重复上一个操作。当查找到根节点即索引值为0时heap构建完成。 程序测试
//heap.h
#pragma once
#include algorithmtemplateclass ForwardIterator
typename std::iterator_traitsForwardIterator::difference_type Distance(ForwardIterator first, ForwardIterator last)
{typename std::iterator_traitsForwardIterator::difference_type n 0;while (first ! last){first;n;}return n;
}templateclass Iterator
inline typename std::iterator_traitsIterator::value_type* value_Type(const Iterator)
{return static_caststd::iterator_traitsIterator::value_type * (0);
}templateclass Iterator
inline typename std::iterator_traitsIterator::difference_type* distance_type(const Iterator)
{return static_caststd::iterator_traitsIterator::difference_type * (0);
}templateclass RandomAcessIterator, class Distance, class T
void _push_heap(RandomAcessIterator first, Distance holeIndex, Distance topIndex, T value)
{Distance parent (holeIndex - 1) / 2;while (holeIndex topIndex *(first parent) value){*(first holeIndex) *(first parent);holeIndex parent;parent (holeIndex-1) / 2;}*(first holeIndex) value;
}templateclass RandomAcessIterator, class Distance, class T
inline void _push_heap_aux(RandomAcessIterator first, RandomAcessIterator last, Distance*, T*)
{int count last - first;_push_heap(first, Distance((last - first) - 1), Distance(0), T(*(last - 1)));
}template class RandomAcessIterator
inline void USD_push_heap(RandomAcessIterator first, RandomAcessIterator last)
{_push_heap_aux(first, last, distance_type(first), value_Type(first));
}templateclass RandomAcessIterator, class Distance, class T
void _adjust_heap(RandomAcessIterator first, Distance holeIndex, Distance len, T value)
{Distance topIndex holeIndex;Distance sencondChild 2 * holeIndex 2;while (sencondChild len){if (*(first sencondChild) *(first sencondChild - 1)){sencondChild--;}*(first holeIndex) *(first sencondChild);holeIndex sencondChild;sencondChild 2 * sencondChild 2;}if (sencondChild len){*(first holeIndex) *(first sencondChild-1);holeIndex sencondChild-1;}_push_heap(first, holeIndex, topIndex,value);
}templateclass RandomAcessIterator,class T,class Distance
inline void _pop_heap(RandomAcessIterator first, RandomAcessIterator last, RandomAcessIterator result,T value,Distance *)
{*result *first;_adjust_heap(first, Distance(0), Distance(last - first), value);
}templateclass RandomAcessIterator,class T
inline void _pop_heap_aux(RandomAcessIterator first, RandomAcessIterator last,T*)
{_pop_heap(first, last-1, last - 1, T(*(last - 1)), distance_type(first));
}templateclass RandomAcessIterator
inline void USD_pop_heap(RandomAcessIterator first, RandomAcessIterator last)
{_pop_heap_aux(first,last,value_Type(first));
}templateclass RandomAcessIterator
void USD_sort_heap(RandomAcessIterator first, RandomAcessIterator last)
{while (last - first1){USD_pop_heap(first,last--);}
}templateclass RandomAcessIterator,class T,class Distance
void _make_heap(RandomAcessIterator first, RandomAcessIterator last, T*, Distance*)
{if (last - first2){return;}Distance len last - first;Distance parent (len - 2) / 2; //最后一个父节点while (true){_adjust_heap(first, parent, len, *(first parent));if (parent 0){return;}parent--;}
}templateclass RandomAcessIterator
inline void USD_make_heap(RandomAcessIterator first, RandomAcessIterator last)
{_make_heap( first,last, value_Type(first), distance_type(first));
}#include heap.h
#include vectorint main()
{int a[5] {1,2,3,4,5};std::vectorint vecTest(a,a5);USD_make_heap(vecTest.begin(), vecTest.end()); //5,4,3,1,2 vecTest.push_back(7);USD_push_heap(vecTest.begin(), vecTest.end()); //7,4,5,1,2,3USD_pop_heap(vecTest.begin(), vecTest.end());//5,4,3,1,2,7vecTest.pop_back();//5,4,3,1,2USD_sort_heap(vecTest.begin(), vecTest.end());//1,2,3,4,5return 0;
}为了方便上述实现都采用了“”作为比较操作符。这块比较操作可封装成仿函数来满足用户自定义的比较操作。注意写仿函数时注意返回的bool值。从而决定构建的是max-heap或者min-heap。 如果想了解算法封装仿函数操作可参考STL算法详细解剖——单纯数据处理函数 此文章列举了相同算法封装仿函数与不封装仿函数两种形式。未了解过仿函数的读者可做初步的了解。
