阅读量:0
目录
堆
如果有一个集合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思路：
- 先将数组拷贝进成员数组中（注意看长度是否够）。
- 我们从最后一棵子树的根节点开始调用shiftDown方法向上一棵一棵树的调整为大根堆。
shiftDown思路：
- 将当前传入的根节点与他的孩子节点将最大值选出作为根。
- 然后将根变成孩子节点再次调整。
- 注意挑选最大值的时候要判断不能让下标越界。
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; } 入堆
代码思路：
- 先判断堆是否已经满了，满了要扩容。
- 在堆最后存入该元素，然后与父亲节点相比较，比父亲节点大就交换，直到到根节点或者比父亲节点小为止。
/** * 入堆：仍然要保持是大根堆 * @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; } 删除
代码思路：
- 先判断堆是否为空，为空直抛空指针异常。
- 我们先将堆顶和堆尾交换，然后向下调整一次。
- 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() | 创建一个空的优先级队列，默认容量是11 |
| PriorityQueue(int initialCapacity) | 创建一个初始容量为initialCapacity的优先级队列，注意initialCapacity不能小于1，否则会抛IllegalArgumentException异常 |
| PriorityQueue(Collection<? extends E> c) | 用一个集合来创建优先级队列 |
常用方法
常用方法如下：
PriorityQueue注意事项
- 使用要导包
import java.util.PriorityQueue; - PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出
ClassCastException异常。 - 不能插入null对象，否则会抛出
NullPointerException。 - 没有容量限制，可以插入任意多个元素，其内部可以自动扩容。
- 如果要将PriorityQueue变成一个大根堆，类实现
Comparator后重写compare方法时将比较改为
public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); } 