3. 图解-什么是堆

清疚 2022-04-15 01:09 278阅读 0赞

### 1. 完全二叉树 ***Complete* binary tree** ###

<table> 
 <tbody> 
 <tr> 
 <td> 
 <ul> 
 <li>Complete&nbsp;binary tree&nbsp;= a&nbsp;binary tree&nbsp;where&nbsp;all&nbsp;levels,&nbsp;except&nbsp;possibly the last level&nbsp;are&nbsp;completely filled&nbsp;with&nbsp;nodes Furthermore:&nbsp;the&nbsp;last level&nbsp;has&nbsp;all&nbsp;its nodes&nbsp;to the&nbsp;left&nbsp;side </li> 
 <li> 完全二叉树= 除最后一层外,每一层上的所有结点都有两个子结点的二叉树, </li> 
 <li> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 而且最后一层所有节点都在左边 </li> 
 </ul></td> 
 </tr> 
 </tbody> 
</table>

完全二叉树例子：

![Complete01b.gif][]

## ##

### 2.什么是堆 ###

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；

或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

### ![1024555-20161217182750011-675658660.png][] ###

![Heap01.gif][] 最小堆

###     因为： ###

1  节点1 的值 是节点1所在子树节点中最小的

![Heap01a.gif][]

###    ###

2  节点5的值 是节点5所在子树中最小的

![Heap01b.gif][]

## ##

3    节点6的值 是节点6所在子树中最小的

![Heap01c.gif][]

### 3.优先队列 ***priority* queue** ###

###      用堆表示优先队列，堆经常被叫做优先队列。 ###

优先队列并不是队列，而是树。Java中，PriorityQueue就是堆（默认是小堆）

在优先队列中，元素被赋予优先级。具有最高级的元素先出 （first in, ***highest* priority** out）

<table> 
 <tbody> 
 <tr> 
 <td> 
 <ul> 
 <li>The&nbsp;job&nbsp;with the&nbsp;highest&nbsp;priority&nbsp;will&nbsp;always&nbsp;be stored in the&nbsp;root&nbsp;node&nbsp;of a&nbsp;heap</li> 
 <li>最高优先级的项目总是存储在堆的根节</li> 
 <li> &nbsp; </li> 
 <li>The&nbsp;heap&nbsp;data structure is&nbsp;often&nbsp;use to store jobs that need to be&nbsp;ranked by their&nbsp;priorities</li> 
 <li>堆 &nbsp;&nbsp; 数据结构经常被用来存储需要按按优先级别排序的数据</li> 
 </ul></td> 
 </tr> 
 </tbody> 
</table>

### 4.参考 ###

[http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/heap-intro.html][http_www.mathcs.emory.edu_cheung_Courses_171_Syllabus_9-BinTree_heap-intro.html]

[Complete01b.gif]: /images/20220415/50911fa4544146408754c94ef0e24921.png
[1024555-20161217182750011-675658660.png]: /images/20220415/c1f6fc401e7848a692bea7b0c282b863.png
[Heap01.gif]: /images/20220415/25425b7ea550422e81fee02adc39faa4.png
[Heap01a.gif]: /images/20220415/873f0f21854e4b76bd4140080e063495.png
[Heap01b.gif]: /images/20220415/31fc5c898610495b9d663ed252eba330.png
[Heap01c.gif]: /images/20220415/712eca7f91fa4ae29df9bb3230e3f844.png
[http_www.mathcs.emory.edu_cheung_Courses_171_Syllabus_9-BinTree_heap-intro.html]: http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/heap-intro.html