愛華網(wǎng)
不談內(nèi)存，從算法上來講紅黑樹插入是最壞情況要比較2logN次(最高的高度）外加不超過兩次旋轉(zhuǎn)，最小堆最壞情況是logN次紅黑樹刪除不需要比較只需要不超過3旋轉(zhuǎn)，查找最小值需要遍歷logN，如果刪除最小值樹調(diào)整一般很小最小堆查詢頂節(jié)點(diǎn)是O(1),而刪除頂節(jié)點(diǎn)在任何情況下都是個(gè)最壞的情況，需要比較2logN次紅黑樹的最壞情況在旋轉(zhuǎn)中不斷調(diào)整變化，插入性能比最小堆差，但刪除最小性能卻比最小堆好上幾倍如果插入+查找最小+刪除最小總體來確定紅黑樹和最小堆，紅黑樹占優(yōu)，性能波動(dòng)相對(duì)較小，紅黑樹不過多的依賴比較，相對(duì)最小堆由比較帶來的的性能影響較?。ㄈ绻容^是調(diào)用自定義函數(shù)、比較的是字符串等，那么性能就犧牲很大）最小堆最大的優(yōu)勢(shì)在于取最小值性能是O(1),如果插入的數(shù)據(jù)基本有序，那么最小堆能獲得比較好的性能，在頻繁不斷地取最小值的是否滿足條件的應(yīng)用中有更加好的性能（如超時(shí)隊(duì)列），紅黑樹相應(yīng)就要盡量避免不必要的查詢次數(shù)才能在超時(shí)隊(duì)列這種應(yīng)用中獲得更好的性能從實(shí)際出發(fā)：由于最小堆一般是采用堆的方式實(shí)現(xiàn)，元素訪問速度遠(yuǎn)高于采用鏈表方式的紅黑樹，插入性能快紅黑樹好幾倍，但最小堆的刪除性能并不快于紅黑樹最小堆的最大缺點(diǎn)就在于必須是連續(xù)的內(nèi)存測試環(huán)境：vmware虛擬機(jī)內(nèi)存1G，cpu1，centos 64， 物理cpu i5 3210m 編譯 O2優(yōu)化，內(nèi)存預(yù)先分配，數(shù)據(jù)預(yù)先生成千萬級(jí)(0-10000000)鏈表方式實(shí)現(xiàn)的最小堆，每次插入刪除都會(huì)涉及到后繼和前驅(qū)的問題，算法復(fù)雜度高一點(diǎn)（從測試結(jié)果來看還比較理想）逆序，刪除最小紅黑樹：insert use time 4.856delete use time 2.142最小堆：insert use time 1.021delete use time 2.015鏈表實(shí)現(xiàn)最小堆：insert use time 3.043delete use time 3.179
順序：紅黑樹:insert use time 5.672delete use time 1.910最小堆：insert use time 0.178delete use time 3.049
鏈表實(shí)現(xiàn)最小堆：insert use time0.243delete use time 4.834
隨機(jī)（測試序列都是一樣，srand（100），然后千萬次rand（）)：紅黑樹：insert use time 15.264delete use time 1.136最小堆：insert use time 0.361delete use time 21.272鏈表實(shí)現(xiàn)最小堆：insert use time0.524delete use time 21.984
