前言
今年年初找工作的时候，参与了京东的面试，在九轮面试的第四轮中面试官出了几道算法题，其中第四道算法题用到了二叉堆，正好最近在整理二叉树相关的知识，在这里记录下。
题目
后来我查，这是一道ACM的题，原题链接
- 1、有m个洗衣机，每台洗衣机只能一件一件洗，没台洗衣机的时间不同。
- 2、有n个烘干机，每台烘干机只能一件一件烘干，没台烘干机的时间不同。
- 3、一共有x件衣服，每件衣服要先洗干净，然后再烘干。
- 求：处理完所有衣服最少的时间是多少？
分析
例行对题目进行拆解，这是一道最优化的问题，优化问题一般的处理方式就是贪心算法。
那么直观的逻辑就是每一件衣服过来，我们都找一个洗的最快的，然后每一件衣服洗完，我们都找一个烘干的最快的，最后总时长就是最短的。
简单来讲是这样，这列又引入到优先队列的问题。然而优先队列的实现呢，是通过二叉堆来实现的。
二叉堆
说道二叉堆，其实就是二叉和堆，这么一听好像是废话。
堆
现实生活的的堆，比如煤堆，沙堆，通畅都是具有一个感性上的物理性质，那么就是个圆锥形，越往上约尖。往沙堆上再扔一把沙子，沙子会滑落到一个稳定的位置，重新保持着这个圆锥的状态，抽象到数据结构中，就是始终有一个大小的关系，整个堆中维护了一个比较关系。在数据结构中，堆就是一种特殊的树形结构，父节点比所有的子节点都大（最大堆），父节点比所有的子节点都小（最小堆）。
二叉堆
说完堆，二叉堆也不难理解，就是用二叉树维护这种大小的关系，父节点比自己的左右节点大的就是最大堆，比左右节点都小的就是最小堆。通畅约定俗成，再说最大堆和最小堆的时候，指的都是二叉堆。
二叉堆除了是二叉树以外，还是一颗完全二叉树，这又是二叉堆的另外一个特性。因为完全二叉树的元素可以通过层级来计算，能够规避掉普通二叉树使用数组实现时的空间浪费问题，通常完全二叉树用数组来存放。
二叉堆的基本操作
除了增删改查基本的数据结构操作，二叉堆本身还有两种特殊的操作。
- 上浮
- 下沉
用最大堆来举例，当堆中插入了一个新元素，将元素置于堆中最后一个元素，然后一路上浮，知道找到一个比自身大的父节点为止。
下沉就是当删除了某个节点，要把这个节点的叶子节点和被删除节点调换位置，然后叶子节点一路下沉，直到一个比自己小的子节点为止。
优先队列
普通队列
普通队列的特点是先入先出，先进的元素最先出队列。
优先队列
其实在普通队列中，也有一个优先的关系，就是最先进入的，最优先处理。优先队列实际上也是为队列中的没个元素维护了一个优先权，优先权最大的元素先出。这个权重可以是元素的大小，可以是元素某个属性的排序前后关系等。
所以优先队列中的元素，必须是可比较的
优先队列利用二叉堆实现
说完了优先队列和二叉堆的特性，也就明白了为什么用二叉堆来实现优先队列，就是因为二叉堆天然的一直在维护一个优先权的关系。
刚才说二叉堆有两个特殊操作，上浮和下沉，优先队列也就是利用了这两个操作完成的维护优先权。
队列的两个基本操作
插入：当队列引入了一个新的元素时，我们利用二叉堆的上浮，重新将队列堆化。
删除：当队列取出某个元素时，我们利用二叉堆的下沉，重新堆化。
网友评论