堆分为小顶堆和大顶堆，其本质是一颗完全二叉树，不同点在于：

除叶子节点外，小顶堆的每个父节点的key都要比其左右两个子节点的key小；大顶堆的每个父节点的key都要比其左右两个子节点的key大。

其中，key是节点的取值，index为节点在树中的索引或者位置。小顶堆/大顶堆的特点在于，其根节点一定是整个数中最小或者最大的元素，这个也是其区别于其他数据结构最大的特点

以大顶堆为例，先来说说其最主要的两个操作add和pop是如何实现的：

.add()

• 在往已有的大顶堆中添加元素时，将新元素作为树的最后的一个节点
• 比较新节点与其父节点：如果新节点的值大于父节点，那么交换父节点和新节点的位置(其实就是交换两个元素的值)
• 重复上述步骤，直到新节点比其父节点小，或者当前新节点的位置已经是根节点了，那么停止上述循环即可，此时大顶堆更新完毕。
  

.pop()

从大顶堆中弹出元素，是指弹出堆的根节点，也就是弹出堆中取值最大的元素。弹出根节点之后，需要对堆进行调整，以使得其还是一个大顶堆

• 将堆的最后一个叶子节点移到根节点的位置
• 从根节点开始，比较根节点和其左右子节点的元素大小，若根节点不是都比子节点大，那么根节点与其较大的一个子节点进行交换
• 只要存在子节点，那么继续比较父节点和左右子节点的大小，直到当前节点已经是叶子节点或者它比它的左右子节点取值都大，那么停止循环，最大堆已经更新完毕
  
  

小顶堆的刚好相反，每一个子树的父节点key值总是小于其两个子节点的key值，因此pop和push方法与大顶堆的原理也十分相似。

参考：

https://zhuanlan.zhihu.com/p/77583063?utm_id=0