C++11STL中常用堆算法有哪些,请详细介绍
时间: 2023-12-10 20:04:14 浏览: 81
C++11STL中常用堆算法有以下几个,分别是:
1. make_heap:将一个序列变成一个堆。
2. push_heap:将一个元素插入到堆中,并保持堆的性质。
3. pop_heap:将堆顶元素移到序列末尾,并保持堆的性质。
4. sort_heap:将一个堆排序。
下面对每个算法进行详细介绍:
1. make_heap
make_heap函数用于将一个序列变成一个堆。其函数原型如下:
```c++
template <class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);
```
其中,first和last分别表示序列的起始位置和结束位置(注意,end位置并不包括在序列内)。
例如,如果有一个整数数组a,我们想要将其变成一个堆,可以这样写:
```c++
int a[] = {3, 1, 4, 1, 5, 9};
make_heap(a, a + 6);
```
这里,a和a+6分别表示数组的起始位置和结束位置。变成堆后,数组a的内容为:{9, 5, 4, 1, 1, 3}。
2. push_heap
push_heap函数用于将一个元素插入到堆中,并保持堆的性质。其函数原型如下:
```c++
template <class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);
```
其中,first和last分别表示序列的起始位置和结束位置(注意,end位置并不包括在序列内)。插入元素之前,序列必须已经是一个堆。
例如,如果有一个整数数组a,其中已经有5个元素,我们想要将一个新元素6插入到堆中,可以这样写:
```c++
int a[] = {9, 5, 4, 1, 1};
push_heap(a, a + 5);
a[5] = 6;
push_heap(a, a + 6);
```
这里,a和a+5分别表示数组的起始位置和结束位置,先将前5个元素变成堆,然后将6插入到数组末尾,再将其插入到堆中。插入后,数组a的内容为:{9, 6, 4, 1, 1, 5}。
3. pop_heap
pop_heap函数用于将堆顶元素移到序列末尾,并保持堆的性质。其函数原型如下:
```c++
template <class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
```
其中,first和last分别表示序列的起始位置和结束位置(注意,end位置并不包括在序列内)。调用该函数之前,序列必须已经是一个堆。
例如,如果有一个整数数组a,其中已经有6个元素,我们想要将堆顶元素弹出,可以这样写:
```c++
int a[] = {9, 6, 4, 1, 1, 5};
pop_heap(a, a + 6);
```
这里,a和a+6分别表示数组的起始位置和结束位置,先将前6个元素变成堆,然后将堆顶元素(9)移到数组末尾。弹出后,数组a的内容为:{6, 1, 4, 1, 5, 9}。
4. sort_heap
sort_heap函数用于将一个堆排序。其函数原型如下:
```c++
template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
```
其中,first和last分别表示序列的起始位置和结束位置(注意,end位置并不包括在序列内)。调用该函数之前,序列必须已经是一个堆。
例如,如果有一个整数数组a,其中已经有6个元素,我们想要将其排序,可以这样写:
```c++
int a[] = {6, 1, 4, 1, 5, 9};
make_heap(a, a + 6);
sort_heap(a, a + 6);
```
这里,a和a+6分别表示数组的起始位置和结束位置,先将数组变成堆,然后进行堆排序。排序后,数组a的内容为:{1, 1, 4, 5, 6, 9}。
阅读全文