在谈堆之前，我们先了解什么是优先队列。我们每天都在排队，银行，医院，购物都得排队。排在队首先处理事情，处理完才能从这个队伍离开，又有新的人来排在队尾。但仅仅这样就能满足我们生活需求吗，明显不能。医院里，患者排队准备看病，这时有个重症患者入队，医生如果按队列的方式一个一个往下处理，等排到这位重病患者时，可能他就因为伤情过重挂了，之后就会引发医患纠纷，这明显不是我们想要的结果。优先队列就成为我们解决此类事情的关键，重病患者入队（挂号），医生根据他的伤情紧急（优先级）优先处理他的病情。

 如果非要用专业术语来区分他们二者的区别

了解了优先队列，那这个堆又是什么玩意，可能很多人听过内存堆栈。特别要声明和注意的是，这里的堆仅仅是存储数据的一种结构方式，与内存的堆栈不是一个概念。

我们先来看下什么是满的二叉树

每一层所有节点都有两个儿子结点的二叉树，就叫满的二叉树，计算他节点个数的公式2^3 - 1 = 7。有七个节点

完全二叉树（最大堆）

知道了什么是堆和优先队列，它们之间有什么关系哪。说穿了就一句话，堆是优先队列这种数据结构的一种实现方式。

注意：优先队列可以用不同的底层实现（普通线性结构），时间复杂度不同。

 也可以定义二叉树来实现完全二叉树，但是通过观察会发现其结构的特点，都是用顺序存储方式存储。从1到n编号，就得到结点的一个线性系列。每一层结点个数恰好是上一层结点个数的2倍，也因此通过一个节点的编号就可以推知他的左右孩子节点的编号。

通过分析和数学归纳得出一个结论，很方便的知道他的左右孩子节点和父节点。

定义一个我们自己的数组Array类，也可以用Java提供的Array

Array类

有了Array数组类，接下来很快的，把我们刚才描述的事情用代码实现出来之后，在考虑出队和入队的操作，因为父节点要大于或小于他们的子节点。所以我们的节点要能相互比较，在Java继承Comparable类就可以了。

最大堆（MaxHeap类）

 向堆中添加一个元素，在堆的内部要进行一个上浮的操作，保证用数组实现的二叉堆还符合我们最大堆的性质（父节点的值大于两个子节点的值）。

82大于他的父节点60，两个结点交换位置，82还大于他的父结点80，两个节点交换位置。80小于现在的父结点90，结束交换。这个操作很多人称为上浮操作（个人认为名称贴切）上浮操作完成。

用代码实现我们刚才的操作，已经知道他父结点的位置（公式），交换两个人的位置就变得很简单，MaxHeap添加函数。

Array类，添加交换位置的函数

有添加就有取出，取出堆中元素其实很简单，因为最大堆决定了只取堆顶元素（数组的第一个元素），直接取出即可。困难的是如何维护二叉堆的性质不变。

取出堆顶元素后

取出堆顶元素，剩下两个子树，将两颗子树糅合成一个二叉堆，现在直接将60这个元素作为堆顶，就满足了完全二叉树的性质但并不符合最大堆性质。

和上浮的操作相反，现在我们要进行下沉的操作，60的左右孩子都比60来得大，要选择左右孩子最大的那个数进行交换，82和60进行交换，80比60来得大，交换他们的位置，10比60来得小，符合二叉堆的性质。交换结束。

用代码描述刚才取出的操作。

MaxHeap类

 现在我们堆结构基本完成，简单测试一下

Main类

输出

用定义的最大堆去实现一个优先队列就变得十分简单了，优先队列本质上来说还是一个队列，用堆来实现队列的接口。

Queue接口类

优先队列（PriorityQueue类）

在股票市场，很多股民向股票代理打电话，股票代理公司优先处理vip客户（有钱￥）再处理普通的用户。把他们的money当做他们的优先程度

Customer类

Main类

输出

随机数，输出结果不确定。但一定是从大到小排序，如果要从小到大很简单，改比较符即可。这边实现的是最大堆，Java提供的优先队列（PriorityQueue）底层是最小堆。

============================================

如发现错误请留言提醒lz，好及时修改，避免误导别人。拜谢