堆

完全二叉树

除了叶子节点外个每一个节点都必须有子节点

二叉堆

二叉堆的定义

二叉堆有最大堆和最小堆的区别，最大堆只保证每个节点的父节点大于当前节点，但不保证上一层节点的值必须大于下一层节点的值，最小堆则与之相反

数组实现二叉堆

数组实现二叉堆的基础（定义各节点在数组中的索引值）

向堆中添加元素

sift up 元素上浮

取出元素

sift down 元素下沉

将一个数组转换成一个最大堆的操作（heapify）

heapify的规则
heapify之后的结构
heapify的操作比循环该数组后再对每个元素进行sift up操作要快速很多，因为它从一开始就抛弃了所有的叶子节点，而只对剩下的节点进行sift down操作
heapify的具体代码其实非常简单
代码

利用堆实现优先队列

利用优先队列来解决leetcode上的第347号问题

https://leetcode-cn.com/problems/top-k-frequent-elements/

定义一个内部类封装每一个元素及其出现的频率

image.png

找出前K个出现频次最高的代码

image.png

利用java内置的优先队列来解决这个问题（java内置的优先队列底层是最小堆实现）

使用比较器（匿名内部类） 不使用lamda表达式 使用lamda表达式

扩展（D叉堆）

d叉堆

此外还有：索引堆，二项堆，斐波那契堆~