std::sort_heap

定義於標頭檔案 `<algorithm>`
template< class RandomIt > void sort_heap( RandomIt first, RandomIt last );	(1)	(C++20 起為 constexpr)
template< class RandomIt, class Compare > void sort_heap( RandomIt first, RandomIt last, Compare comp );	(2)	(C++20 起為 constexpr)

將堆 [first, last) 轉換為已排序的範圍。堆屬性不再保持。

1) 堆是關於operator<(C++20 前)std::less{}(C++20 起)的，並將按operator<(C++20 前)std::less{}(C++20 起)進行排序。

2) 堆是關於 comp 的，並將按 comp 進行排序。

如果滿足以下任何條件，則行為是未定義的：

[first, last) 不是堆。

*first 的型別不是可交換 (Swappable)的。	(C++11 前)
`RandomIt` 不是可值交換的 (ValueSwappable)。 first 的型別不是可移動構造 (MoveConstructible)的。 first 的型別不是可移動賦值 (MoveAssignable)的。	(C++11 起)

first, last	-	定義要轉換為排序範圍的二叉堆元素範圍的迭代器對
comp	-	比較函式物件（即滿足比較 (Compare)要求的一個物件），若首個引數“小於”第二個，則返回 true。比較函式的簽名應等效於以下內容 bool cmp(const Type1& a, const Type2& b); 雖然簽名不必有 const&，但函式不得修改傳遞給它的物件，並且必須能夠接受 `Type1` 和 `Type2` 型別的所有值（可能是 const），而不論其值類別（因此不允許 Type1&，也不允許 Type1，除非對於 `Type1` 移動等價於複製(C++11 起)）。型別 Type1 和 Type2 必須使得型別 RandomIt 的物件可以解引用，然後隱式轉換為這兩種型別。
型別要求
- `RandomIt` 必須滿足舊式隨機訪問迭代器 (LegacyRandomAccessIterator)的要求。
- `Compare` 必須滿足 Compare 的要求。

[編輯] 複雜度

給定 $\scriptsize N$ $N$ 為 std::distance(first, last)

1) 至多

2N\cdotlog(N)

次比較，使用operator<(C++20 前)std::less{}(C++20 起)。

2) 至多

2N\cdotlog(N)

次呼叫比較函式 comp。

[編輯] 可能的實現

sort_heap (1)

template<class RandomIt>
void sort_heap(RandomIt first, RandomIt last)
{
    while (first != last)
        std::pop_heap(first, last--);
}

sort_heap (2)

template<class RandomIt, class Compare>
void sort_heap(RandomIt first, RandomIt last, Compare comp)
{
    while (first != last)
        std::pop_heap(first, last--, comp);
}

[編輯] 示例

執行此程式碼

#include <algorithm>
#include <iostream>
#include <string_view>
#include <vector>
 
void println(std::string_view fmt, const auto& v)
{
    for (std::cout << fmt; const auto &i : v)
        std::cout << i << ' ';
    std::cout << '\n';
}
 
int main()
{
    std::vector<int> v{3, 1, 4, 1, 5, 9};
 
    std::make_heap(v.begin(), v.end());
    println("after make_heap, v: ", v);
 
    std::sort_heap(v.begin(), v.end());
    println("after sort_heap, v: ", v);
}

輸出

after make_heap, v: 9 4 5 1 1 3
after sort_heap, v: 1 1 3 4 5 9

[編輯] 缺陷報告

下列更改行為的缺陷報告追溯地應用於以前出版的 C++ 標準。

缺陷報告	應用於	釋出時的行為	正確的行為
LWG 2444	C++98	允許至多 $\scriptsize N \cdot \log(N)$ $N\cdotlog(N)$ 次比較	增加到 $\scriptsize 2N \cdot \log(N)$ $2N\cdotlog(N)$

[編輯] 參閱

is_heap (C++11)	檢查給定的範圍是否是一個最大堆 (函式模板) [編輯]
is_heap_until (C++11)	尋找是一個最大堆的最大子範圍 (函式模板) [編輯]
make_heap	從一個元素範圍建立一個最大堆 (函式模板) [編輯]
pop_heap	從一個最大堆中移除最大的元素 (函式模板) [編輯]
push_heap	向一個最大堆新增一個元素 (函式模板) [編輯]
ranges::sort_heap (C++20)	將一個最大堆轉換成一個按升序排序的元素範圍 (演算法函式物件)[編輯]

編譯器支援
自由（freestanding）與宿主（hosted）
語言
標準庫
標準庫標頭檔案
具名要求
特性測試宏 (C++20)
語言支援庫
概念庫 (C++20)
診斷庫
記憶體管理庫
超程式設計庫 (C++11)
通用工具庫
容器庫
迭代器庫
範圍庫 (C++20)
演算法庫
字串庫
文字處理庫
數值庫
日期和時間庫
輸入/輸出庫
檔案系統庫 (C++17)
併發支援庫 (C++11)
執行控制庫 (C++26)
技術規範
符號索引
外部庫

cppreference.com

名稱空間

變體

檢視

操作