数据结构之堆和优先队列

堆

可以说是树的一种，很类似树的结构，我们在这里只是研究二叉堆，二叉堆是一棵完全二叉树，满二叉树也是一个完全二叉树（完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。）。 总的来说，完全二叉树就是只有最后一层不满。 然后就是堆得定义，堆可以分为最大堆和最小堆，最大堆，就是根是最大的，根在所有的节点中是最大的，在最大的堆中，每一个父节点永远大于子节点，根节点的值最大。

存储

我们使用数组进行存储堆，这个时候我们就要去计算数组中的下标和堆中的元素的关系，我们可以通过画图来完成。 这就是我们画的图，如果我们要组成一个数组，就是{60,40,30,8,9}，下标非别为01234，我们就要开始找规律，一个结点下标为i，他的父亲节点是i-1/2，他的左孩子节点为2i+1，他的右孩子节点是2i+2，我们举个例子，40，这个节点，他的下标是1，它的父节点是1-1/2=0，是0节点，他的孩子节点，左孩子12+1=3，右孩子12+2=4,。例子还有好多读者可以去测试一下。

构造

private Array<E> data; public MaxHeap(int capacity) { data= new Array<E>(capacity); } public MaxHeap() { data=new Array<E>() ; } /** * 这个构造实现了将一个数组转换为一个堆，从第一个非叶子结点开始做起 * 不断下沉 * @param arr */ public MaxHeap(E[] arr) { data=new Array<>(arr); for (int i = parent(arr.length-1); i >=0; i--) { siftDown(i); } }

因为上面我们讨论了如何使用数组去存储一个堆。所以我们的底层可以采用数组，并不是矛盾，并且我们可以生成一个构造，传入一个数组完成一个堆这里使用的还有一个叫做siftDown的方法。

/** * 重新排序根节点 * 在最后面的元素一定是最小的 * 把最小的元素放在最大的位置，这个是堆左子树和右子树是没有大小的区别的 * 找到最小的根的最小的子孩子 * @param k */ private void siftDown(int k) { while(leftChild(k)<data.getSize()) { //有左孩子 int j=leftChild(k); //找到他的左孩子 if(j + 1<data.getSize()&& data.get(j+1).compareTo(data.get(j))>0) { j=rightChild(k); } //data[j]是最大的元素 if(data.get(k).compareTo(data.get(j))>=0) { break; } data.swap(k, j); k=j; //交换根节点 } }

因为传进来的数组可能并不是第一个元素是最大的，所以我们要把最大的元素放在第一个，我们在构造中定义了，这个循环循环遍历是从后面开始的，传到我们siftDown(i);中的是，每一个元素的父节点，首先上来先判断leftChild(k)<data.getSize()是否有左孩子，如果没有左孩子一定是没有右孩子的，如果有就让int j=leftChild(k);是他的左孩子，然后下面判断他是否有右孩子并且他的右孩子是否比左孩子要大，如果都满足j=rightChild(k); 也就是说我们需要去判断谁是最大的，拿到左右孩子中最大的那个元素，然后去跟父节点进行比对，如果父节点大则不交换，如果父节点不如子节点大，交换。

基础代码

/** * 找到堆的长度 * @return */ public int size() { return data.getSize(); } /** * 判断堆是否为空 * @return */ public boolean isEmpty () { return data.isEmpty(); } /** * 下面的三个方法是找他的双亲的，找他的孩子的， * 至于减一加一是因为从零开始 */ /** * 找到他的根节点 * @param index * @return */ private int parent(int index) { if(index==0) { throw new IllegalArgumentException("meiyouroot"); } return (index-1)/2; } /** * 找到左子树的位置 * @param index * @return */ private int leftChild(int index) { return index*2+1; } /** * 找到右子树的位置 * @param index * @return */ private int rightChild(int index) { return index*2+2; }

这部分的代码是一些比较基础的代码，一个获得长度一个判断是否为空的，有三个是我们的功能函数，就是一个判断左孩子，右孩子，父节点。

元素的增加

public void add(E e) { data.addList(e); siftUP(data.getSize()-1); } /** *上浮，如果大就交换小就算了 * @param k */ private void siftUP(int k){ while(k>0 && data.get(parent(k)).compareTo(data.get(k))<0) { data.swap(k, parent(k)); k=parent(k); } } public void swap(int i,int j) { if(i<0 || i>=size || i<0 || j>=size) { throw new IllegalArgumentException("index is ILL"); } E e=data[i]; data[i]=data[j]; data[j]=e; }

元素的增加的逻辑，元素增加以后，直接增加在末尾，然后通过我们的一个函数上浮，siftUP，如果k>0并且增加的节点大于增加的节点的父节点就交换两个节点，然后将k值等于根的父节点，递归进行遍历它的父节点，如果不行牵扯的子树是不需要去变得。 在这里实现了一个swap的方法，这个方法是用来交换两个元素的，将两个元素传入就可以交换他们在堆中的位置。

元素的删除

因为是最大堆，所以这一项可以相当于删除最大的元素，我们用最大的元素来代替删除元素。

/** * 删除并返回最大的 */ public E extractMax() { E ret=findMax(); data.swap(0, data.getSize()-1); data.removeLast(); siftDown(0); return ret; } public E findMax() { if(data.getSize()==0){ throw new IllegalArgumentException("堆 为 空"); } return data.get(0); }

在这里是是实现了对于元素的删除，先找到最大的元素，就是这个堆的根，如果没有根，先抛出一个异常，找到根以后，我们可以再将最后一个元素和根交换，然后删除最后一个元素。 先说说为什么要这么去做，就是因为我们删除的根节点如果由根节点的左右子树直接继承，会很麻烦，因为不管是由左子树继承还是右子树继承，一旦变成了根那么，他就需要去继承剩下的子树，但是他本身就是有左右的子树，所以我们要去选一个使整个堆变化最少的，就是使用最后一个元素，也就是最下面一层最靠右的元素，因为他一定没有子树，不会有其他的变化，我们把它和根节点进行交换，然后删除掉最后一个节点，这就可以完成了。 我们在这里的代码的实现就是找到最大的的元素，和最后一个元素进行交换，然后去删掉最后一个元素，然后去使用siftDown重新进行排序，siftDown的原理在上边有，就是实现这个方法去是所有的元素按照堆的顺序开始排列，返回之前的根元素。

元素的替换

/** * 去除根最大的元素，并且替换为元素e * @param e * @return */ public E replace(E e){ E ret=findMax(); data.set(0, e); siftDown(0); return ret; }

取出一个堆的根，然后去替换这个根，然后如果我们后面添加的这个元素没有我们根大，我们就使用下沉siftDown一直下沉到最后一个元素。

优先队列

什么叫做优先队列呢？看字面意思，是队列的一种，但是具体是什么呢？ 优先队列，也是队的一种，但是这个队并不是先进先出，而是谁的优先级高或者是谁更加的重要谁先出队，所以是需要去遍历整个队的结构找出谁的优先级是最高的。 在这里需要看我们是用什么样子的数据结构做底层？ 如果使用普通的数组，入队就是普通的O(1)，但是出队需要去遍历所有的，O(n) 如果采用的是链表，则入队的时候可以排好序，O(n)，出队的话只需要出一个头就可以了O(1)。 但是如果我们采用的是堆，那我们出队入队采用的都是O(logn)。 我们就使用堆来进行尝试。

构造

private MaxHeap<E> max; public PriorityQueue() { max=new MaxHeap<E>(); }

使用一个堆作为底层，构造函数new 一个堆。

普通方法

@Override public int getsize() { // TODO Auto-generated method stub return max.size(); } @Override public boolean isEmpty() { // TODO Auto-generated method stub return max.isEmpty(); } /** * 为空抛异常 */ @Override public E getfront() { // TODO Auto-generated method stub return max.findMax(); } @Override public void enqueue(E e) { // TODO Auto-generated method stub max.add(e); } @Override public E dequeue() { // TODO Auto-generated method stub return max.extractMax(); }

普通的方法都是实现了Queue这个接口的方法，用也是在堆中的方法。 这就是我对于堆和优先队列一些认识，有错误请大家指出来。