二叉堆

• 是完全二叉树的一种，有两类
• 最大堆：堆顶最大，根节点比两个孩子大于或等于
• 最小堆：堆顶最小，根节点比两个孩子小于或等于
• 是堆排序和优先队列的基础

二叉堆插入节点

在最后一个树叶节点插入，会上浮到合适位置以保持顺序稳定

二叉堆删除节点

从堆顶删除，会把最后一个节点补充过去，然后下沉到合适位置以保持顺序稳定

构建二叉堆

非叶子节点依次下沉到合适位置

二叉堆代码实现

顺序存储，故使用数组，并使用二叉堆的数组定位方式

优先队列

-对应二叉堆，有两种

• 最大优先队列，每次都是最大元素出队
• 最小优先队列，每次都是最小元素出队
• 入队和出队的时间复杂度均为O(log n)

优先队列入队

对应二叉堆插入节点，会从树叶节点上浮

优先队列出队

对应二叉堆删除节点，会从堆顶节点下沉

优先队列代码实现

以二叉堆为基础，自然和它一样用数组

数据结构基础--二叉堆、优先队列

原文：https://www.cnblogs.com/j-c-y/p/11544107.html