up:: Programming
source:: バイナリヒープの概要
ヒープとは最小又は最大の値が必ず最初に来る配列。
残りの値は親子関係を作りつつ下へ伸びていく。
そのうち、最大2つ迄しか子を持たないヒープがバイナリヒープ。
子を一つしか持っていない親に、子が一つの親はつけられない。0なら可能。
この場合、親と子のインデックスには次の関係が成り立つ。
Math.floorは小数点切り捨て。
childIndex = 2n+1 or 2n+2parentIndex = Math.floor((n-1)/2)値を新しく挿入すると、親の値と比較する形で昇っていく。
最上位の値を抽出する場合、まず一番下と値を交換してから取り出し、この値を比較して降りていく。
up:: Cpp
source:: make_heap - cpprefjp C++日本語リファレンス
source:: C++ で STL ヒープアルゴリズムを使用する | Delft スタック
source:: push_heap - cpprefjp C++日本語リファレンス
source:: pop_heap - cpprefjp C++日本語リファレンス
source:: pop_heap
source:: c++ - std::make_heap with pairs - Stack Overflow
cppでは、std::make_heapで既存のコンテナをヒープ化。std::sort_heapで最大最小を入れ替え再ヒープ化。
抽出はstd::pop_heapを使う。これ自体は先頭の要素を最後尾と入れ替えた後、最後尾を除いたコンテナをヒープ化する関数。なので使った後にback()とpop_back()などを使うことでヒープを崩さず最大値を抽出できる。
入力は普通にpush_backなどで入れた後、std::push_heapを使い再ヒープ化。結果的にはstd::make_heapと変わらないが、書いてることを見る限り、std::push_heapは一つ追加しただけのヒープに対してだけ使える関数で、std::make_heapより軽いっぽい。
ヒープ化関数は比較演算子が無いと動かない。が、引数に比較用の関数を入れる部分があるので、タプルなど単純比較できないコンテナでも処理することが出来る。強み。
up:: Unreal_Engine
source:: 2,646行もあるUE4のTArrayのヒミツ. ということで、Unreal Engine 4 (UE4) Advent… | by Isoparametric | Medium
source:: TArray::Heapify | Unreal Engine Documentation
source:: C++演算子オーバーロード大全 - Qiita
source:: 【C++】既存のクラスを拡張する方法【拡張メソッド／カテゴリ】 | MaryCore
source:: TArray::HeapPop | Unreal Engine Documentation
source:: パフォーマンスを高めるために TArray の使用を最適化する - Unreal Engine
UEではTArray::Heapifyを使う。こっちは比較関数は入れられないので注意。なんとかして比較演算子をコンテナに実装できればワンチャンあるかも。
抽出はTArray::HeapPop。こっちは引数に消した値を取り出す関数。
とりあえず値だけ消したいなら、TArray::HeapPopDiscardを使う。
消さないけど最大値だけ欲しいならTArray::HeapTop。