手撸优先队列——二叉堆

优先队列也是队列，那么最基本的两个操作是必须有的，那就是入队和出队操作。我们能想到的几种简单的实现方法有，比如一个简单的链表，入队时就在链表的最后添加元素，那么出队时就要遍历整个链表，找出最小元素，这显然不是一个好的方案。或者我们直接使用AVL平衡二叉树，最小元素就是最左侧的子节点，很容易找到，但是在入队和出队的过程中，涉及到了节点的增加和删除，那么就要进行树的旋转而维持树的平衡，这额外花费了很多开销。那么有没有相对廉价一点的方案呢？这就是
二叉堆的方案。