在谈堆之前，我们先了解什么是优先队列。我们每天都在排队，银行，医院，购物都得排队。排在队首先处理事情，处理完才能从这个队伍离开，又有新的人来排在队尾。但仅仅这样就能满足我们生活需求吗，明显不能。医院里，患者排队准备看病，这时有个重症患者入队，医生如果按队列的方式一个一个往下处理，等排到这位重病患者时，可能他就因为伤情过重挂了，之后就会引发医患纠纷，这明显不是我们想要的结果。优先队列就成为我们解决此类事情的关键，重病患者入队（挂号），医生根据他的伤情紧急（优先级）优先处理他的病情。
如果非要用专业术语来区分他们二者的区别
队列先进先出，后进后出
优先队列，出队与入队时的顺序无关，与优先级有关。
堆了解了优先队列，那这个堆又是什么玩意，可能很多人听过内存堆栈。特别要声明和注意的是，这里的堆仅仅是存储数据的一种结构方式，与内存的堆栈不是一个概念。
二叉堆是一颗完全二叉树结构（不懂什么是树的同学请面壁），说的通俗点，堆就是满足一些特殊性质的树，所以二叉堆就是有特殊性质的二叉树。
父节点的值大于（小于）两个子节点的值，又称为最大堆和最小堆，我们要定义的是最大堆（最小堆跟他相反）。
实例我们先来看下什么是满的二叉树
每一层所有节点都有两个儿子结点的二叉树，就叫满的二叉树，计算他节点个数的公式2^3 - 1 = 7。有七个节点
完全二叉树（最大堆）
知道了什么是堆和优先队列，它们之间有什么关系哪。说穿了就一句话，堆是优先队列这种数据结构的一种实现方式。
注意：优先队列可以用不同的底层实现（普通线性结构），时间复杂度不同。
数组实现完全二叉树（最大堆）也可以定义二叉树来实现完全二叉树，但是通过观察会发现其结构的特点，都是用顺序存储方式存储。从1到n编号，就得到结点的一个线性系列。每一层结点个数恰好是上一层结点个数的2倍，也因此通过一个节点的编号就可以推知他的左右孩子节点的编号。
通过分析和数学归纳得出一个结论，很方便的知道他的左右孩子节点和父节点。
父节点 parent(i) = （i - 1） / 2，算下结点10的父节点 (7 - 1) / 2 = 3 就是 60
左孩子 left child(i) = 2 * i + 1，可以算出 10 的左孩子 7 * 2 + 1 = 15 > 7 (这里的7为最大索引值)没有左孩子这个结点
右孩子 right child(i) = 2 * i + 2,可以算出 10 的右孩子 7 * 2 + 2 = 16 > 7 没有右孩子这个结点
定义一个我们自己的数组Array类，也可以用Java提供的Array
Array类
public class Array<E> { private E[] data; private int size; //构造函数，传入数组的容量capacity构造Array public Array(int capacity) { this.data = (E[]) new Object[capacity]; size = 0; } //无参数构造函数 public Array() { this(10); } //获取数组的个数 public int getSize() { return size; } //获取数组的容量 public int getCapacity() { return data.length; } //数组是否为空 public boolean isEmpty() { return size == 0; } //添加最后一个元素 public void addLast(E e) { add(size,e); } //添加第一个元素 public void addFirst(E e){ add(0,e); } //获取inde索引位置的元素 public E get(int index){ if (index < 0 || index >= size){ throw new IllegalArgumentException("Get failed,index is illegal"); } return data[index]; } public void set(int index,E e){ if (index < 0 || index >= size){ throw new IllegalArgumentException("Get failed,index is illegal"); } data[index] = e; } //获取最后一个元素 public E getLast(){ return this.get(size - 1); } //获取第一个元素 public E getFirst(){ return this.get(0); } //添加元素 public void add(int index,E e){ if (index > size || index < 0){ throw new IllegalArgumentException("add failed beceause index > size or index < 0,Array is full."); } if (size == data.length){ resize(data.length * 2); } for (int i = size - 1; i >= index; i--) { data[i+1] = data[i]; } data[index] = e; size ++; } //扩容数组 private void resize(int newCapacity) { E[] newData = (E[]) new Object[newCapacity]; for (int i = 0; i < size; i++) { newData[i] = data[i]; } data = newData; } public E[] getData() { return data; } //查找数组中是否有元素e public boolean contains(E e){ for (int i = 0; i < size; i++) { if (data[i].equals(e)){ return true; } } return false; } //根据元素查看索引 public int find(E e){ for (int i = 0; i < size; i++) { if (data[i].equals(e)){ return i; } } return -1; } //删除某个索引元素 public E remove(int index){ if(index < 0 || index >= size){ throw new IllegalArgumentException("detele is fail,index < 0 or index >= size"); } E ret = data[index]; for (int i = index + 1; i < size; i++) { data[i - 1] = data[i]; } size --; data[size] = null; if (size < data.length / 2){ resize(data.length / 2); } return ret; } //删除首个元素 public E removeFirst(){ return this.remove(0); } //删除最后一个元素 public E removeLast(){ return this.remove(size - 1); } //从数组删除元素e public void removeElemen(E e){ int index = find(e); if (index != -1){ remove(index); } } @Override public String toString() { StringBuilder sb = new StringBuilder(""); sb.append(String.format("Array:size = %d,capacity = %d \n",size,data.length)); sb.append("["); for (int i = 0; i < size; i++) { sb.append(data[i]); if (i != size - 1){ sb.append(","); } } sb.append("]"); return sb.toString(); } }