# 二叉堆详解实现优先级队列
**通知：算法可视化编辑器上线，[点击体验](https://labuladong.online/algo/intro/visualize/)！另外，建议你在我的 [网站](https://labuladong.online/algo/) 学习文章，体验更好。**
**-----------**
二叉堆（Binary Heap）没什么神秘，性质比二叉搜索树 BST 还简单。
其主要操作就两个，`sink`（下沉）和 `swim`（上浮），用以维护二叉堆的性质。其主要应用有两个，首先是一种排序方法「堆排序」，第二是一种很有用的数据结构「优先级队列」。
那么本文以实现优先级队列（Priority Queue）为例，来讲讲一下二叉堆怎么运作的。
### 一、二叉堆概览
首先，二叉堆和二叉树有啥关系呢，为什么人们总是把二叉堆画成一棵二叉树？
引用本文的文章
- [Dijkstra 算法模板及应用](https://labuladong.online/algo/fname.html?fname=dijkstra算法)
- [双指针技巧秒杀七道链表题目](https://labuladong.online/algo/fname.html?fname=链表技巧)
- [如何调度考生的座位](https://labuladong.online/algo/fname.html?fname=座位调度)
- [快速排序详解及应用](https://labuladong.online/algo/fname.html?fname=快速排序)
- [设计朋友圈时间线功能](https://labuladong.online/algo/fname.html?fname=设计Twitter)
引用本文的题目
安装 [我的 Chrome 刷题插件](https://labuladong.online/algo/intro/chrome/) 点开下列题目可直接查看解题思路：
| LeetCode | 力扣 |
| :----: | :----: |
| [1104. Path In Zigzag Labelled Binary Tree](https://leetcode.com/problems/path-in-zigzag-labelled-binary-tree/?show=1) | [1104. 二叉树寻路](https://leetcode.cn/problems/path-in-zigzag-labelled-binary-tree/?show=1) |
| [1845. Seat Reservation Manager](https://leetcode.com/problems/seat-reservation-manager/?show=1) | [1845. 座位预约管理系统](https://leetcode.cn/problems/seat-reservation-manager/?show=1) |
| [23. Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/?show=1) | [23. 合并K个升序链表](https://leetcode.cn/problems/merge-k-sorted-lists/?show=1) |
| [347. Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/?show=1) | [347. 前 K 个高频元素](https://leetcode.cn/problems/top-k-frequent-elements/?show=1) |
| [451. Sort Characters By Frequency](https://leetcode.com/problems/sort-characters-by-frequency/?show=1) | [451. 根据字符出现频率排序](https://leetcode.cn/problems/sort-characters-by-frequency/?show=1) |
| [662. Maximum Width of Binary Tree](https://leetcode.com/problems/maximum-width-of-binary-tree/?show=1) | [662. 二叉树最大宽度](https://leetcode.cn/problems/maximum-width-of-binary-tree/?show=1) |
| [692. Top K Frequent Words](https://leetcode.com/problems/top-k-frequent-words/?show=1) | [692. 前K个高频单词](https://leetcode.cn/problems/top-k-frequent-words/?show=1) |
| [703. Kth Largest Element in a Stream](https://leetcode.com/problems/kth-largest-element-in-a-stream/?show=1) | [703. 数据流中的第 K 大元素](https://leetcode.cn/problems/kth-largest-element-in-a-stream/?show=1) |
| - | [剑指 Offer 40. 最小的k个数](https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/?show=1) |
| - | [剑指 Offer II 059. 数据流的第 K 大数值](https://leetcode.cn/problems/jBjn9C/?show=1) |
| - | [剑指 Offer II 060. 出现频率最高的 k 个数字](https://leetcode.cn/problems/g5c51o/?show=1) |
| - | [剑指 Offer II 078. 合并排序链表](https://leetcode.cn/problems/vvXgSW/?show=1) |
**＿＿＿＿＿＿＿＿＿＿＿＿＿**
本文为会员内容，请扫码关注公众号或 [点这里](https://labuladong.online/algo/ds-class/dong-shou--b9ca2/er-cha-dui-1a386) 查看：
======其他语言代码======
### javascript
```js
/**
* 最大堆
*/
function left(i) {
return i * 2 + 1;
}
function right(i) {
return i * 2 + 2;
}
function swap(A, i, j) {
const t = A[i];
A[i] = A[j];
A[j] = t;
}
class Heap {
constructor(arr) {
this.data = [...arr];
this.size = this.data.length;
}
/**
* 重构堆
*/
rebuildHeap() {
const L = Math.floor(this.size / 2);
for (let i = L - 1; i >= 0; i--) {
this.maxHeapify(i);
}
}
isHeap() {
const L = Math.floor(this.size / 2);
for (let i = L - 1; i >= 0; i++) {
const l = this.data[left(i)] || Number.MIN_SAFE_INTEGER;
const r = this.data[right(i)] || Number.MIN_SAFE_INTEGER;
const max = Math.max(this.data[i], l, r);
if (max !== this.data[i]) {
return false;
}
return true;
}
}
sort() {
for (let i = this.size - 1; i > 0; i--) {
swap(this.data, 0, i);
this.size--;
this.maxHeapify(0);
}
}
insert(key) {
this.data[this.size++] = key;
if (this.isHeap()) {
return;
}
this.rebuildHeap();
}
delete(index) {
if (index >= this.size) {
return;
}
this.data.splice(index, 1);
this.size--;
if (this.isHeap()) {
return;
}
this.rebuildHeap();
}
/**
* 堆的其他地方都满足性质
* 唯独跟节点，重构堆性质
* @param {*} i
*/
maxHeapify(i) {
let max = i;
if (i >= this.size) {
return;
}
// 求左右节点中较大的序号
const l = left(i);
const r = right(i);
if (l < this.size && this.data[l] > this.data[max]) {
max = l;
}
if (r < this.size && this.data[r] > this.data[max]) {
max = r;
}
// 如果当前节点最大，已经是最大堆
if (max === i) {
return;
}
swap(this.data, i, max);
// 递归向下继续执行
return this.maxHeapify(max);
}
}
module.exports = Heap;
```
