堆栈算法笔记

堆栈算法笔记"/>

堆栈算法笔记

堆栈都是一种数据项按序排列的数据结构，只能在一端(称为栈顶(top))对数据项进行插入和删除。

堆（数据结构）：堆可以被看成是一棵树，如：堆排序。进出顺序随意
栈（数据结构）：一种先进后出的数据结构。

std::make_heap将[start, end)范围进行堆排序，默认使用less, 即最大元素放在第一个。

• make_heap()是生成一个堆，大顶堆或小顶堆
• make_heap(_RAIter,_RAIter) 默认生成大顶堆
• make_heap(_RAIter,_RAIter,_Compare)
  _Compare有两种参数，一种是greater（生成小顶堆），一种是less（生成大顶堆）

std::pop_heap将front（即第一个最大元素）移动到end的前部，同时将剩下的元素重新构造成(堆排序)一个新的heap。

• pop_heap()是在堆的基础上，弹出堆顶元素。
• pop_heap(_RAIter,_RAIter) 默认为大顶堆
• pop_heap(_RAIter,_RAIter,_Compare)
  _Compare有两种参数，一种是greater（小顶堆），一种是less（大顶堆）
• 比如pop_heap(nums.begin(),
  nums.end(),greater())，它会将堆顶元素（即为数组第一个位置）和数组最后一个位置对调，然后你可以调用数组pop_back，删除这个元素
• 注意，pop_heap中的_Compare和make_heap中的_Compare参数必须是一致的，不然会失败

std::push_heap对刚插入的（尾部）元素做堆排序。

• push_heap()是向堆中插入一个元素，并且使堆的规则依然成立
• push_heap(_RAIter,_RAIter) 默认为大顶堆
• push_heap(_RAIter,_RAIter,_Compare)
  _Compare有两种参数，一种是greater（小顶堆），一种是less（大顶堆）
• 调用push_heap之前必须调用make_heap创建一个堆
• 首先数组push_back插入元素，然后再调用push_heap，它会使最后一个元素插到合适位置
• 注意，push_heap中的_Compare和make_heap中的_Compare参数必须是一致的，不然会插入堆失败，最后一个元素还是在最后位置，导致插入失败

std::sort_heap将一个堆做排序,最终成为一个有序的系列

可以看到sort_heap时，必须先是一个堆（两个特性：1、最大元素在第一个
2、添加或者删除元素以对数时间），因此必须先做一次make_heap.

fill函数

有时候，我们可能需要对某一块数据进行初始化,那么std库就提供了一个函数来进行初始化fill()

• 函数原型
  fill函数在头文件 中声明：

template< class ForwardIt, class T >
void fill( ForwardIt first, ForwardIt last, const T& value );

参数解析:
first,last:所需要修改元素的范围(地址)
value:数据块所赋的值