C++堆 小結(jié)

重點(diǎn)回顧

• 堆是一棵完全二叉樹，根據(jù)成立條件可分為大頂堆和小頂堆。大（?。╉敹训亩秧斣厥亲畲螅ㄐ。┑?。
• 優(yōu)先隊(duì)列的定義是具有出隊(duì)優(yōu)先級(jí)的隊(duì)列，通常使用堆來(lái)實(shí)現(xiàn)。
• 堆的常用操作及其對(duì)應(yīng)的時(shí)間復(fù)雜度包括：元素入堆 O(log?n)、堆頂元素出堆 O(log?n) 和訪問(wèn)堆頂元素 O(1) 等。
• 完全二叉樹非常適合用數(shù)組表示，因此我們通常使用數(shù)組來(lái)存儲(chǔ)堆。
• 堆化操作用于維護(hù)堆的性質(zhì)，在入堆和出堆操作中都會(huì)用到。
• 輸入 n 個(gè)元素并建堆的時(shí)間復(fù)雜度可以優(yōu)化至 O(n) ，非常高效。
• Top-K 是一個(gè)經(jīng)典算法問(wèn)題，可以使用堆數(shù)據(jù)結(jié)構(gòu)高效解決，時(shí)間復(fù)雜度為 O(nlog?k) 。

Q & A

數(shù)據(jù)結(jié)構(gòu)的“堆”與內(nèi)存管理的“堆”是同一個(gè)概念嗎？

兩者不是同一個(gè)概念，只是碰巧都叫堆。計(jì)算機(jī)系統(tǒng)內(nèi)存中的堆是動(dòng)態(tài)內(nèi)存分配的一部分，程序在運(yùn)行時(shí)可以使用它來(lái)存儲(chǔ)數(shù)據(jù)。程序可以請(qǐng)求一定量的堆內(nèi)存，用于存儲(chǔ)如對(duì)象和數(shù)組等復(fù)雜結(jié)構(gòu)。當(dāng)這些數(shù)據(jù)不再需要時(shí)，程序需要釋放這些內(nèi)存，以防止內(nèi)存泄露。相較于棧內(nèi)存，堆內(nèi)存的管理和使用需要更謹(jǐn)慎，不恰當(dāng)?shù)氖褂每赡軙?huì)導(dǎo)致內(nèi)存泄露和野指針等問(wèn)題。