一、概述

• 二叉堆，使用sink、swim来维护二叉堆的性质，应用于堆排序和优先级队列；
• 二叉堆在逻辑上是一种完全二叉树，只不过存储在数组中；

• 链表二叉树中我们操作节点的指针，数组中使用数组索引作为指针

  二、结构

  

• 数组第一个索引空着不用

• arr[1]作为根，每个节点的父节点和左右孩子的索引都可以通过简单的运算得到
• 最大堆：每个节点都大于等于其子节点

• 最小堆：每个节点都小于等于其子节点

  三、优先级队列

• 插入或者删除元素的时候，元素会自动排序，这底层的原理就是二叉堆的操作;

• 主要API：insert插入一个元素，delMax删除最大的元素;

• 插入元素会破坏堆的性质，就需要swim、sink操作来恢复

  四、实现

• insert：将元素添加至末尾，然后swim实现堆的性质

• delMax：将堆顶元素和堆底元素互换，删除堆底元素，然后对堆顶元素进行sink