【数据结构】堆,优先级队列-LMLPHP

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

堆的性质

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

大根堆的模拟实现

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

接口实现

接口成员方法。

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来表示优先级队列,其底层是一个小根堆。

实现的接口

【数据结构】堆,优先级队列-LMLPHP

构造方法

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

常用方法

常用方法如下:
【数据结构】堆,优先级队列-LMLPHP

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个数

07-26 02:23