C++

參考

<algorithm>

function template
<algorithm>

std::push_heap

預設 (1)
template <class RandomAccessIterator>  void push_heap (RandomAccessIterator first, RandomAccessIterator last);
自定義 (2)
template <class RandomAccessIterator, class Compare>  void push_heap (RandomAccessIterator first, RandomAccessIterator last,                   Compare comp);
將元素推入堆範圍
給定範圍[first,last-1)中的一個堆，該函式透過將(last-1)中的值放置到其相應位置來將範圍擴充套件為[first,last)。

可以透過呼叫make_heap將一個範圍組織成一個堆。在此之後，如果使用push_heap和pop_heap分別從堆中新增和刪除元素，其堆屬性將得以保留。

引數

first, last
隨機訪問迭代器指向新堆範圍的起始和結束位置，包括被推入的元素。使用的範圍是[first,last)，它包含first和last之間的所有元素，包括first指向的元素，但不包括last指向的元素。
comp
二進位制函式，它接受範圍中的兩個元素作為引數，並返回一個可轉換為bool的值。返回的值指示第一個引數是否被認為在它定義的特定*嚴格弱序*中小於第二個引數。
除非[first,last)是空範圍或只有一個元素的堆，否則此引數應與構建堆時使用的引數相同。
該函式不得修改其任何引數。
這可以是指標函式，也可以是函式物件。

返回值

無

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
// range heap example
#include <iostream>     // std::cout
#include <algorithm>    // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
#include <vector>       // std::vector

int main () {
  int myints[] = {10,20,30,5,15};
  std::vector<int> v(myints,myints+5);

  std::make_heap (v.begin(),v.end());
  std::cout << "initial max heap   : " << v.front() << '\n';

  std::pop_heap (v.begin(),v.end()); v.pop_back();
  std::cout << "max heap after pop : " << v.front() << '\n';

  v.push_back(99); std::push_heap (v.begin(),v.end());
  std::cout << "max heap after push: " << v.front() << '\n';

  std::sort_heap (v.begin(),v.end());

  std::cout << "final sorted range :";
  for (unsigned i=0; i<v.size(); i++)
    std::cout << ' ' << v[i];

  std::cout << '\n';

  return 0;
}

輸出
initial max heap   : 30
max heap after pop : 20
max heap after push: 99
final sorted range : 5 10 15 20 99


複雜度

複雜度為first和last之間距離的對數：比較元素並可能交換（或移動）它們，直到重新排列成一個更長的堆。

資料競爭

範圍[first,last)中的一些（或全部）物件被修改。

異常

如果任何元素比較、元素交換（或移動）或迭代器操作丟擲異常，則會丟擲異常。
請注意，無效引數會導致未定義行為。

另見

make_heap
從範圍建立堆 （函式模板）
pop_heap
從堆範圍中彈出元素 （函式模板）
sort_heap
對堆的元素進行排序 （函式模板）
reverse
反轉範圍 （函式模板）