目录

• 堆
• 堆的性质
• 大根堆的模拟实现
• • 接口实现
  • 构造方法
  • 建堆
  • 入堆
  • 判满
  • 删除
  • 判空
  • 获取堆顶元素
• Java中的PriorityQueue
• • 实现的接口
  • 构造方法
  • 常用方法
  • PriorityQueue注意事项
• 练习

堆

如果有一个集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质

• 堆逻辑结构上是一棵完全二叉树。
• 堆上的节点一定不大于（大根堆）或者不小于（小根堆）父亲节点。

大根堆的模拟实现

使用代码来实现一个大根堆。

接口实现

接口成员方法。

public class PriorityQueue {     public int[] elem;     public int usedSize;     public PriorityQueue() {}     //建堆     public void createHeap(int[] array) {}     /**      * @param root 是每棵子树的根节点的下标      * @param len  是每棵子树调整结束的结束条件      * 向下调整的时间复杂度：O(logn)      */     private void shiftDown(int root,int len) {}     // 入堆：仍然要保持是大根堆     public void push(int val) {}     private void shiftUp(int child) {}     //判断堆是否满     public boolean isFull() {}     //每次删除的都是优先级高的元素,删除后任是大根堆     public void pollHeap() {}     //判断堆是否为空     public boolean isEmpty() {}      // 获取堆顶元素     public int peekHeap() {} } 

构造方法

在构造方法中构建为长度10的数组。

public PriorityQueue() {         elem = new int[10];     } 

建堆

createHeap思路：

1. 先将数组拷贝进成员数组中（注意看长度是否够）。
2. 我们从最后一棵子树的根节点开始调用shiftDown方法向上一棵一棵树的调整为大根堆。

shiftDown思路：

1. 将当前传入的根节点与他的孩子节点将最大值选出作为根。
2. 然后将根变成孩子节点再次调整。
3. 注意挑选最大值的时候要判断不能让下标越界。

 public void createHeap(int[] array) {         if(elem.length < array.length){             elem = Arrays.copyOf(elem, elem.length * 2);         }         for (int i = 0; i < array.length; i++){             elem[i] = array[i];             usedSize++;         }         for (int root = (usedSize -1 -1) / 2; root >= 0 ; root--) {             shiftDown(root,usedSize);         }     }      /**      * @param root 是每棵子树的根节点的下标      * @param len  是每棵子树调整结束的结束条件      * 向下调整的时间复杂度：O(logn)      */     private void shiftDown(int root,int len) {         int child = root * 2 + 1;         while (child < len){             //寻找孩子节点的大值             if(child + 1 < len && elem[child] < elem[child + 1]){                 child++;             }             if(elem[root] < elem[child]){                 swap(elem,root,child);                 root = child;                 child = root * 2 + 1;             }else {                 break;             }         }     }     //交换函数     private void swap(int[] array,int x,int y){         int tmp = array[x];         array[x] = array[y];         array[y] = tmp;     } 

入堆

代码思路：

1. 先判断堆是否已经满了，满了要扩容。
2. 在堆最后存入该元素，然后与父亲节点相比较，比父亲节点大就交换，直到到根节点或者比父亲节点小为止。

	 /**      * 入堆：仍然要保持是大根堆      * @param val      */     public void push(int val) {         if(isFull()){             elem = Arrays.copyOf(elem, elem.length*2);         }         elem[usedSize] = val;         shiftUp(usedSize);         usedSize++;     }     private void shiftUp(int child) {         int parent = (child - 1) / 2;         while(parent >= 0) {             if (elem[parent] < elem[child]) {                 swap(elem, parent, child);                 child = parent;                 parent = (child - 1) / 2;             }else {                 break;             }         }     } 

判满

这个方法直接使用成员变量usedSize和数组长度判断即可。

public boolean isFull() {         return usedSize == elem.length;     } 

删除

代码思路：

1. 先判断堆是否为空，为空直抛空指针异常。
2. 我们先将堆顶和堆尾交换，然后向下调整一次。
3. useds减1。

ublic void pollHeap() throws NullPointerException {         if (isEmpty()) {             throw new NullPointerException();         }         swap(elem,0,usedSize-1);         shiftDown(0,usedSize);         usedSize--;     } 

判空

这个方法直接使用成员变量usedSize是否为0就行。

public boolean isEmpty() {         return usedSize == 0;     } 

获取堆顶元素

如果堆为空，抛空指针异常，没有直接返回堆顶元素。

public int peekHeap() throws NullPointerException {         if (isEmpty()) {             throw new NullPointerException();         }         return elem[0];     } 

Java中的PriorityQueue

在Java中使用集合类PriorityQueue来表示优先级队列，其底层是一个小根堆。

实现的接口

构造方法

提供了以下3种构造方法：

常用方法

常用方法如下：

PriorityQueue注意事项

1. 使用要导包import java.util.PriorityQueue;
2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常。
3. 不能插入null对象，否则会抛出NullPointerException。
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容。
5. 如果要将PriorityQueue变成一个大根堆，类实现Comparator后重写 compare方法时将比较改为

public int compare(Integer o1, Integer o2) {         return o2.compareTo(o1);     } 

练习

最小k个数