二叉堆 主要操作： sink（下沉） 和 上浮（swin），用以维护二叉堆的性质，其主要应用有两个，首先是一种排序方法，堆排序，其次是一种数据结构，优先级队列。
二叉堆和二叉树的关系：二叉堆在逻辑上其实就是一种特殊的二叉树（完全二叉树），只不过存储在数组里
一般的链表二叉树，我们操作链表节点的指针，而在数组中我们把数组的下标（索引）作为指针。
父节点的索引：
int parent ( int root ) {
return root / 2 ;
}
int leftChild ( int root ) {
return root * 2 ;
}
int rightChild ( int root ) {
return root * 2 + 1 ;
}
如图：
二叉堆分为最大堆和最小堆，最大堆：每个节点都大于等于它的两个子节点，最小堆：每个节点都小于等于它的两个子节点
优先级队列一个很有用的功能就是，你插入或者删除元素的时候，元素会自动排序，底层的原理就是二叉堆的操作。
数据结构的功能无非就是增删改查，优先级队列主要有两个API，分别是insert插入一个元素和delMax删除一个元素（delMin）。
public class MaxPQ
<Key extends Comparable<Key>> {
// 存储元素的数组
private Key[] pq;
// 当前 Priority Queue 中的元素个数
private int size = 0;
public MaxPQ(int cap) {
// 索引 0 不用，所以多分配一个空间
pq = (Key[]) new Comparable[cap + 1];
}
/* 返回当前队列中最大元素 */
public Key max() {
return pq[1];
}
/* 插入元素 e */
public void insert(Key e) {...}
/* 删除并返回当前队列中最大元素 */
public Key delMax() {...}
/* 上浮第 x 个元素，以维护最大堆性质 */
private void swim(int x) {...}
/* 下沉第 x 个元素，以维护最大堆性质 */
private void sink(int x) {...}
/* 交换数组的两个元素 */
private void swap(int i, int j) {
Key temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
/* pq[i] 是否比 pq[j] 小？ */
private boolean less(int i, int j) {
return pq[i].compareTo(pq[j]) < 0;
}
/* 还有 left, right, parent 三个方法 */
}
实现 swim 和 sink
为什么要有上浮 swim 和下沉 sink 的操作呢？为了维护堆结构
最大堆，每个节点都比它的两个子节点大，但是在插入元素和删除元素时，难免破坏堆的性质，这就需要通过这两个操作来恢复堆的性质了。
对于最大堆，会破坏堆性质的有两种情况：
1、如果某个节点 A 比它的子节点（中的一个）小，那么 A 就不配做父节点，应该下去，下面那个更大的节点上来做父节点，这就是对 A 进行下沉。
2、如果某个节点 A 比它的父节点大，那么 A 不应该做子节点，应该把父节点换下来，自己去做父节点，这就是对 A 的上浮。
当然，错位的节点 A 可能要上浮（或下沉）很多次，才能到达正确的位置，恢复堆的性质。所以代码中肯定有一个 while 循环。
这两个操作不是互逆吗，所以上浮的操作一定能用下沉来完成，为什么我还要费劲写两个方法？
是的，操作是互逆等价的，但是最终我们的操作只会在堆底和堆顶进行（等会讲原因），显然堆底的「错位」元素需要上浮，堆顶的「错位」元素需要下沉。
上浮的代码实现：
private void swim(int x) {
// 如果浮到堆顶，就不能再上浮了
while (x > 1 && less(parent(x), x)) {
// 如果第 x 个元素比上层大
// 将 x 换上去
swap(parent(x), x);
x = parent(x);
}
}下沉的代码实现：
下沉比上浮略微复杂一点，因为上浮某个节点 A，只需要 A 和其父节点比较大小即可；但是下沉某个节点 A，需要 A 和其两个子节点比较大小，如果 A 不是最大的就需要调整位置，要把较大的那个子节点和 A 交换。
private void sink(int x) {
// 如果沉到堆底，就沉不下去了
while (left(x) <= size) {
// 先假设左边节点较大
int max = left(x);
// 如果右边节点存在，比一下大小
if (right(x) <= size && less(max, right(x)))
max = right(x);
// 结点 x 比俩孩子都大，就不必下沉了
if (less(max, x)) break;
// 否则，不符合最大堆的结构，下沉 x 结点
swap(x, max);
x = max;
}
}实现 delMax 和 insert
这两个方法就是建立在 swim 和 sink 上的。
insert 方法先把要插入的元素添加到堆底的最后，然后让其上浮到正确位置。
public void insert(Key e) {
size++;
// 先把新元素加到最后
pq[size] = e;
// 然后让它上浮到正确的位置
swim(size);
}
delMax 方法先把堆顶元素 A 和堆底最后的元素 B 对调，然后删除 A，最后让 B 下沉到正确位置。
public Key delMax() {
// 最大堆的堆顶就是最大元素
Key max = pq[1];
// 把这个最大元素换到最后，删除之
swap(1, size);
pq[size] = null;
size--;
// 让 pq[1] 下沉到正确位置
sink(1);
return max;
}至此，一个优先级队列就实现了，插入和删除元素的时间复杂度为 O(logK)，K 为当前二叉堆（优先级队列）中的元素总数。因为我们时间复杂度主要花费在 sink 或者 swim 上，而不管上浮还是下沉，最多也就树（堆）的高度，也就是 log 级别。
二叉堆就是一种完全二叉树，所以适合存储在数组中，而且二叉堆拥有一些特殊性质。
二叉堆的操作很简单，主要就是上浮和下沉，来维护堆的性质（堆有序），核心代码也就十行。
优先级队列是基于二叉堆实现的，主要操作是插入和删除。插入是先插到最后，然后上浮到正确位置；删除是调换位置后再删除，然后下沉到正确位置。
标签：pq,优先级,队列,元素,二叉,int,上浮,节点 From： https://www.cnblogs.com/fuqiangblog/p/16734238.html