Faiss最大堆實現
基本概念
1) 以一個數組作為存儲，但數據結構實際是一個二叉樹
2) 二叉樹的某個節點大於等於它的所有子節點，但同一個層次的左右（子）節點大小未知，所以該堆（數組）的第一個元素必然是最大值（當然最大值有可能會出現在多個元素）
3) 存儲方式為，如果數組的序號從1開始，那麼v(i)>=v(2i)以及v(2i+1)，即序號為i的節點如果存在直接子節點（最多2個），那麼直接子節點是2i 和 2i+1（如果都存在的話）
初始化
比起普通的堆，Faiss的堆還附帶了另一個id數組
template <class C> inline
void heap_heapify (
size_t k,
typename C::T * bh_val,
typename C::TI * bh_ids,
const typename C::T * x = nullptr,
const typename C::TI * ids = nullptr,
size_t k0 = 0)
{
if (k0 > 0) assert (x);
if (ids) {
for (size_t i = 0; i < k0; i++)
heap_push<C> (i+1, bh_val, bh_ids, x[i], ids[i]);
} else {
for (size_t i = 0; i < k0; i++)
heap_push<C> (i+1, bh_val, bh_ids, x[i], i);
}
for (size_t i = k0; i < k; i++) {
bh_val[i] = C::neutral();
bh_ids[i] = -1;
}
}
輸入
1) k 是需要初始化的堆的元素個數
2) bh_val 待初始化的堆所在數組，在faiss中指返回距離數組
3) bh_ids 一個附加返回，對應返回距離對應的id（id指來自與查詢比較的一個目標索引集合）
4) x 有可能需要定製的距離初始值，個數為k0, 默認為空
5) ids 有可能需要定製的距離x對應的元素id,個樹為k0，默認為空
6) k0 需要定製的距離的個數，默認為0
執行
1） 如果有需要定製的距離數組x和ids, 那麼先用定製數組初始化的堆bh_val以及對應的bh_ids ，默認是不需要的
2) 既然已經初始了k0個元素，那麼後面只需要初始化k-k0就可以了，默認k0 為0
3) 默認的初始化是指bh_val堆中所有元素值為std::numeric_limits<float>::max(),即3.40282347e+38，bh_ids ,默認全為-1
初始化完畢後變成了
pop
template <class C> inline
void heap_pop (size_t k, typename C::T * bh_val, typename C::TI * bh_ids)
{
bh_val--; /* Use 1-based indexing for easier node->child translation */
bh_ids--;
typename C::T val = bh_val[k];
size_t i = 1, i1, i2;
while (1) {
i1 = i << 1;
i2 = i1 + 1;
if (i1 > k)
break;
if (i2 == k + 1 || C::cmp(bh_val[i1], bh_val[i2])) {
if (C::cmp(val, bh_val[i1]))
break;
bh_val[i] = bh_val[i1];
bh_ids[i] = bh_ids[i1];
i = i1;
}
else {
if (C::cmp(val, bh_val[i2]))
break;
bh_val[i] = bh_val[i2];
bh_ids[i] = bh_ids[i2];
i = i2;
}
}
bh_val[i] = bh_val[k];
bh_ids[i] = bh_ids[k];
}
輸入
1) 堆的大小，即數組的個數
2) bh_val 即需要處理的堆
3) bh_ids 堆中元素對應的id(id解釋見上文)
處理
1) 由於數組的實際存儲序號是從0開始，為了方便計算（原因見基本概念部分），首先將指針為前挪了一位
2) 此時bh_val[1]是最大的根節點，左子節點和右子節點分別為i<<1和i<<+1, 比較左子節點、右子節點、還有最後一個元素3者之間的大小
2.1) 如果左節點節點較大，那麼進入左子樹，否則進入右子樹
2.2） 通常情況下，根據最大堆的概念，最後一個元素< 較大的子樹，此時是需要一個騰挪的，所謂騰挪比如較大左子點分別是元素2,元素4,元素9，元素18，元素18是最後一個元素，那麼此時就需要元素2挪到根節點，元素4挪到元素2,元素9挪到元素4,元素18挪到元素9，所以通常情況下整個程序會不斷的沿著樹的較大子節點下探
2.3) 不知道為啥有2個break,通常情況下最後一個葉子節點肯定不會大於某個較大的葉子節點，所以這個 break不大會執行，除非數據問題
3) bh_ids 本身也不是堆，只是bh_vals對應的一個id數組，隨著bh_vals的變化就好
總之
功能是彈出堆的第一個元素，即堆中最大值，然後將堆中第二大值填充到第一個元素，再將其他元素逐個騰挪補位，直到最後一元素也騰挪完畢，此時最後一個元素已失去意義，為接下來的push做準備
push
template <class C> inline
void heap_push (size_t k,
typename C::T * bh_val, typename C::TI * bh_ids,
typename C::T val, typename C::TI ids)
{
bh_val--; /* Use 1-based indexing for easier node->child translation */
bh_ids--;
size_t i = k, i_father;
while (i > 1) {
i_father = i >> 1;
if (!C::cmp (val, bh_val[i_father])) /* the heap structure is ok */
break;
bh_val[i] = bh_val[i_father];
bh_ids[i] = bh_ids[i_father];
i = i_father;
}
bh_val[i] = val;
bh_ids[i] = ids;
}
輸入
1) 堆的大小，即數組的個數
2) bh_val 即需要處理的堆
3) bh_ids 堆中元素對應的id(id解釋見上文)
4) val 待push的那個距離
5) id val對應的id
處理
1) 堆指針前挪一位的解釋見上文
2) 由於最後一個值是無效的，所以push的那個值就需要和最後那個元素的對應的父節點，父節點的父節點......，直到根節點，看看比較適合放在哪個位置，比如還是以堆的大小是18,那麼最後一個元素是18, 依次往上的父子關係是1(v1),2(v2),4(v4),9(v9),18(無效值), 如果此時待插入的元素x在v2,v4之間，那麼插入x元素之後，會變成1(v1),2(v2),4(x),9(v4),18(v9), 堆中其他位置的元素不變
3) bh_ids的處理push
一個例子
heap 初始值
{3.40282347e+38, 3.40282347e+38, 3.40282347e+38, 3.40282347e+38}
{-1, -1, -1, -1}
1.輸入10.5144215
pop:
{3.40282347e+38, 3.40282347e+38, 3.40282347e+38, 3.40282347e+38}
{-1, -1, -1, -1}
push
{3.40282347e+38, 3.40282347e+38, 3.40282347e+38, 10.5144215}
{-1, -1, -1, 0}
2. 輸入0
pop:
{3.40282347e+38, 3.40282347e+38, 10.5144215, 10.5144215}
{-1, -1, 0, 0}
push:
{3.40282347e+38, 3.40282347e+38, 10.5144215, 0}
{-1, -1, 0, 1}
3.輸入10.2842665
pop:
{3.40282347e+38, 0, 10.5144215, 0}
{-1, 1, 0, 1}
push:
{3.40282347e+38, 10.2842665, 10.5144215, 0}
{-1, 2, 0, 1}
4.輸入15.4879131
pop:
{10.5144215, 10.2842665, 0, 0}
{0, 2, 1, 1}
push
{15.4879131, 10.5144215, 0, 10.2842665}
{3, 0, 1, 2}
5 .輸入12.4123116
pop:
{10.5144215, 10.2842665, 0, 10.2842665}
{0, 2, 1, 2}
push
{12.4123116, 10.5144215, 0, 10.2842665}
{4, 0, 1, 2}
6 輸入9.3830843
pop:
{10.5144215, 10.2842665, 0, 10.2842665}
{0, 2, 1, 2}
push
{10.5144215, 10.2842665, 0, 9.3830843}
{0, 2, 1, 5}
堆排序
template <typename C> inline
size_t heap_reorder (size_t k, typename C::T * bh_val, typename C::TI * bh_ids)
{
size_t i, ii;
for (i = 0, ii = 0; i < k; i++) {
/* top element should be put at the end of the list */
typename C::T val = bh_val[0];
typename C::TI id = bh_ids[0];
/* boundary case: we will over-ride this value if not a true element */
heap_pop<C> (k-i, bh_val, bh_ids);
bh_val[k-ii-1] = val;
bh_ids[k-ii-1] = id;
if (id != -1) ii++;
}
/* Count the number of elements which are effectively returned */
size_t nel = ii;
memmove (bh_val, bh_val+k-ii, ii * sizeof(*bh_val));
memmove (bh_ids, bh_ids+k-ii, ii * sizeof(*bh_ids));
for (; ii < k; ii++) {
bh_val[ii] = C::neutral();
bh_ids[ii] = -1;
}
return nel;
}
輸入
1) 堆的大小，即數組的個數
2) bh_val 即需要處理的堆
3) bh_ids 堆中元素對應的id(id解釋見上文)
處理
1) 核心部分是第一個for循環
2) pop出一個最大元素，並將最大元素到當前堆的最後一個位置（如上文提到由於pop之後，這個最後一個位置失去意義）
3) 每次pop都會縮小堆元素的範圍，不斷重複執行上一步
4) 第一個for循環是為了處理一些邊界條件，為了防止一些無效的id，一旦出現這種無效id，最後統一補齊
推薦閱讀：
