堆就是用數(shù)組實(shí)現(xiàn)的二叉樹

所有它沒有使用父指針或者子指針。堆根據(jù)“堆屬性”來排序，“堆屬性”決定了樹中節(jié)點(diǎn)的位置。

堆的常用方法：

? ? ?構(gòu)建優(yōu)先隊(duì)列

? ? 支持堆排序

? ? 快速找出一個集合中的最小值（或者最大值）

堆屬性

堆分為兩種：最大堆和最小堆，兩者的差別在于節(jié)點(diǎn)的排序方式。

在最大堆中，父節(jié)點(diǎn)的值比每一個子節(jié)點(diǎn)的值都要大。在最小堆中，父節(jié)點(diǎn)的值比每一個子節(jié)點(diǎn)的值都要小。這就是所謂的“堆屬性”，并且這個屬性對堆中的每一個節(jié)點(diǎn)都成立。

例子：

這是一個最大堆，，因?yàn)槊恳粋€父節(jié)點(diǎn)的值都比其子節(jié)點(diǎn)要大。10比7和2都大。7比5和1都大。

根據(jù)這一屬性，那么最大堆總是將其中的最大值存放在樹的根節(jié)點(diǎn)。而對于最小堆，根節(jié)點(diǎn)中的元素總是樹中的最小值。堆屬性非常的有用，因?yàn)槎殉３１划?dāng)做優(yōu)先隊(duì)列使用，因?yàn)榭梢钥焖俚脑L問到“最重要”的元素。

注意：堆的根節(jié)點(diǎn)中存放的是最大或者最小元素，但是其他節(jié)點(diǎn)的排序順序是未知的。例如，在一個最大堆中，最大的那一個元素總是位于 index 0 的位置，但是最小的元素則未必是最后一個元素。--唯一能夠保證的是最小的元素是一個葉節(jié)點(diǎn)，但是不確定是哪一個。