本文主要是介绍了解C++中STL的堆操作:构建、拆解和排序 堆(Heap),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
在C++中使用STL构建、拆解和排序堆
- 一、简介
- 二、std::push_heap
- 三、std::pop_heap
- 四、std::sort_heap
- 五、总结
一、简介
首先要要熟悉堆(Heap)是什么以及它们是如何工作的,如果你不知道什么是堆(Heap),可以先阅读前面的文章,再来看这篇文章会更好。
好了,现在假设你已经清楚堆(Heap),可以使用C++的STL来构建堆、拆解堆和对堆进行排序。
以一个堆(Heap)的例子开始:
这是一个最大堆,最大的元素在顶部。我们将插入一个元素(这与C++并没有太大关系),它是如何在堆数据结构中插入一个元素。
二、std::push_heap
在堆的末尾添加8.8
。这并不是它正确的位置,所以将使它通过堆向上移动。将它与其父元素进行比较,每当它大于其父元素时,就对它们进行交换:
这样它最终会到达它的最终位置。
在C++中,堆被表示为连续的结构,例如在std::vector
中。因此,将这个堆压缩成一个数组。
现在要添加一个元素,将在向量的末尾push_back
这个元素,并调用std::push_heap
,使这个最后一个元素向其最终位置在堆中向上移动:
std::vector myHeap = // ... 有关std::make_heap,请参见前面的文章
myHeap.push_back(8.8);
std::push_heap(begin(myHeap), end(myHeap));
三、std::pop_heap
那么如何从堆中删除一个元素?只能删除一个元素,即顶部的元素。为了做到这一点,可以使用std::pop_heap
。它首先将想要删除的第一个元素与最小的其中一个元素(即最后一个元素)进行交换。
然后,它将使这个小元素在堆中向下移动到其最终位置,通过与其子元素进行比较。每当它小于其中一个子元素时,将它与其最大的子元素交换,以确保能够保持堆的特性。
为了实际去掉曾经在堆顶的元素,它现在位于verctor
中的最后位置,在vector
上执行一个pop_back
:
std::pop_heap(begin(myHeap), end(myHeap));
myHeap.pop_back();
四、std::sort_heap
仔细思考以下,如果重复执行std::pop_heap
操作但不把vector
中的元素取出来,那么顶部的元素就会按排序顺序堆积在vector
的末尾。
这样做的次数越多,堆中的元素就越多,最终得到的是一个排序好的vector
,不再有堆(Heap)。
这基本上是std::sort_heap
所做的事情:
std::sort_heap(begin(myHeap), end(myHeap));
它接收一个堆并对其进行排序,其复杂度最大为2*N*log(N)
。
五、总结
以上就是使用STL操纵堆(Heap)的全部内容。这里看到了如何使用std::push_heap
构建堆,如何使用std::pop_heap
拆解堆,以及如何使用std::sort_heap
对堆进行排序。
这篇关于了解C++中STL的堆操作:构建、拆解和排序 堆(Heap)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!