堆是一棵完全二叉樹，使用數(shù)組實現(xiàn)堆，堆分為兩種：
1.最大堆：父節(jié)點大于任意子節(jié)點（因此堆頂為最大值）
2.最小堆：父節(jié)點小于任意子節(jié)點（因此堆頂為最小值）
對于第i個節(jié)點（i從0開始計數(shù)）：
1.父節(jié)點：(i-1)/2
2.左子節(jié)點：2i+1
3.右子節(jié)點：2i+2
若包含sz個節(jié)點，則第一個非葉子節(jié)點的序號為(sz - 2) / 2

插入節(jié)點
插入節(jié)點時，進行下列操作：
?將元素添加到數(shù)組末尾；（相當于葉節(jié)點接入堆中）
?和父節(jié)點進行比較，如果大于父節(jié)點(以最大堆為例)，則與父節(jié)點交換，一直比較交換到根節(jié)點

向堆中插入元素
*hole：新元素所在的位置

template <class value> void _push_heap(vector<value> &arr,int hole)

總結(jié)

以上是生活随笔為你收集整理的C++堆的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。