std::make_heap

預設 (1)	template <class RandomAccessIterator> void make_heap (RandomAccessIterator first, RandomAccessIterator last);
自定義 (2)	template <class RandomAccessIterator, class Compare> void make_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp );

預設 (1)

template <class RandomAccessIterator>  void make_heap (RandomAccessIterator first, RandomAccessIterator last);

自定義 (2)

template <class RandomAccessIterator, class Compare>  void make_heap (RandomAccessIterator first, RandomAccessIterator last,                  Compare comp );

將範圍轉換為堆

重排範圍 [first,last) 中的元素，使其構成一個堆。

堆是一種組織範圍元素的方式，它允許隨時快速檢索具有最高值的元素（使用 pop_heap），甚至可以重複檢索，同時還允許快速插入新元素（使用 push_heap）。

具有最高值的元素始終由 first 指向。其他元素的順序取決於具體實現，但在該標頭檔案的所有堆相關函式中是一致的。

元素透過 operator<（對於第一個版本）或 comp（對於第二個版本）進行比較：具有最高值的元素是指在與範圍中的任何其他元素進行比較時，該元素返回 false 的元素。

標準容器介面卡 priority_queue 會自動呼叫 make_heap、push_heap 和 pop_heap 來維護容器的堆屬性。

引數

first, last: 指向序列的初始位置和最終位置的隨機訪問迭代器，該序列將被轉換為堆。使用的範圍是 [first,last)，它包含 first 和 last 之間的所有元素，包括 first 指向的元素，但不包括 last 指向的元素。
RandomAccessIterator 應指向一個型別，該型別 swap 已正確定義，並且是可移動構造和可移動賦值的。
comp: 二元函式，它接受範圍中的兩個元素作為引數，並返回一個可轉換為 bool 的值。返回的值指示第一個引數傳遞的元素在其定義的特定嚴格弱序中是否被認為小於第二個元素。
該函式不得修改其任何引數。
這既可以是函式指標，也可以是函式物件。

返回值

無

示例

// 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)內的物件將被修改。

異常

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

另見

push_heap: 將元素推入堆範圍（函式模板）

pop_heap: 從堆範圍中彈出元素（函式模板）

sort_heap: 對堆的元素進行排序（函式模板）

reverse: 反轉範圍（函式模板）