堆的基本操作和PriorityQueue接口

目录

堆的插入

堆的删除

PriorityQueue接口

PriorityQueue的注意事项:

PriorityQueue常用接口介绍

  1. 优先级队列的介绍

  2.  扩容

  3. 插入/删除/获取优先级最高的元素

Java对象的比较

       1.基本类型的比较

       2.对象比较的问题

       3.对象比较的方法

Top- k问题

---

堆的插入

堆的插入总共分为两个步骤:

        1:先将元素放到底层空间中(空间不够的时候要扩容)

        2:将新插入的节点向上调整,直到满足大根堆或者小根堆的性质(以大根堆为例)

代码实现:

public void offer(int val) {
        if(isFull()) {
            //扩容
            Arrays.copyOf(elem,2*elem.length);
        }
        //放到最后一个位置
        elem[usedSize++] = val;
        //向上调整
        shiftUp(usedSize- 1);
    }
    //判断是否满了
    public boolean isFull() {
        return usedSize == elem.length;
    }
    //向上调整
    private void shiftUp(int child) {
        int parent = (child-1) / 2;
        while(child > 0) {
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child-1) / 2;
            } else {
                break;
            }
        }
    }

向上调整建堆的时间复杂度:

---

 堆的删除

注意:堆的删除一定是删除堆顶元素

        1: 将堆顶元素和堆中有效数据的最后一个数据交换

        2: 将有效长度减1(最后一个元素就被删除)

        3: 对堆顶元素进行向下调整

代码实现:

public void pop(int val) {
        if(isEmpty()) {
            return;
        }
        int tmp = elem[0];
        elem[0] = elem[usedSize-1];
        elem[usedSize-1] = tmp;
        usedSize--;
        shifDown(0,usedSize);
    }
    //判断是否为空
    public boolean isEmpty() {
        return usedSize == 0;
    }
    //向下调整
    public void shifDown(int parent,int len) {
        int child = 2 * parent + 1;
        //最起码有一个左孩子
        while (child < len) {
            //有右孩子的情况
            if (child + 1 < len && elem[child] < elem[child + 1]) {
                //保证child下标是左右孩子最大值下标
                child++;
            }
            if (elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

---

PriorityQueue接口

java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的. 本文主要介绍PriorityQueue.

---

PriorityQueue的注意事项:

1. 在使用PriorityQueue时要导入所在包

2. PriorityQueue中放置的元素必须能够比较大小,不能插入无法比较大小的对象,否则会抛出classCastException.

3. 不能插入null对象,否则会抛出NUllPointException.

4. 没有容量限制,可以任意插入多个元素,其内部可以自动扩容

5. 插入和删除的时间复杂度为O(log2 N)

6. PriorityQueue底层使用了堆数据结构

7. PriorityQueue默认底层为小根堆.每次获取到的都是最小的元素.

---

PriorityQueue常用接口介绍

        1. 优先级队列的介绍

代码实现 :

  一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好

  否则在插入时需要扩容

扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低

---

  2.  扩容

---

  3. 插入/删除/获取优先级最高的元素

我们在调用这个接口的时候,这些方法可以直接被使用.

---

     

Java对象的比较

       1.基本类型的比较

在Java中,基本数据类型可以直接进行比较

运行结果:

       

         2.对象比较的问题

从编译结果来看,Java中引用类型的变量不能直接使用 > 或者 <的方式进行比较,那 == 为什么可以呢?

因为:用户实现自定义类型,都默认继承自Object类,而Object类提供了equal方法,而==默认情况下调用的就是equal方法,但是该方法的比较规则是:没有比较引用变量引用的对象,而是直接比较引用变量的地址.

        3.对象比较的方法

        1.重写equals方法

在上面创建的两个Student对象,他们的名字和年龄都相同,意味着他俩是同一个Student.而在重写equals方法中只要年龄和名字相同就返回true.

equal只能按照相等进行比较,本能按照大于 , 小于的方式进行比较.

       

         2.基于Comparable接口类的比较

如果想按照大小的方式进行比较,在自定义类时,实现Comparble接口即可,然后重写compareTo方法.但这种方法还是存在缺陷,就像上面代码显示一样,只能按照年龄进行比较,不能按照其他变量进行比较.

       

        3.基于比较器的比较

代码表示: 

我们想用什么变量比较就实现Comparble接口即可,然后重写compareTo方法.

---

Top- k问题

TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大.

思路:

1. 用数据集合中的前 k 个元素来建堆

        ● 前k个最大元素 :建小根堆

        ●前k个最小元素 : 建大根堆

2. 用剩余的N-k个元素和堆顶元素进行比较 , 不满足则替换堆顶元素 ,

将剩余的N-k 个元素依次和堆顶元素比较 , 堆中剩余的元素就是前K个最大的或者最小的元素.

用比较器构造大根堆和小根堆

代码实现前k个最大元素 :

java中默认使用的是小根堆,在求前k个最大元素的时候可以不使用比较器建小根堆

 public int[] maxK(int[] arr,int k) {
        int ret[] = new int[k];
        if(arr == null || k == 0) {
            return ret;
        }
        //建立K个元素的小根堆
        Queue<Integer> minHeap = new PriorityQueue<>(k);
        //遍历数组的前K个,放到堆中
        for (int i = 0; i < k; i++) {
            minHeap.offer(arr[i]);
        }
        //遍历剩下的k-1个,和堆顶元素比较
        // 堆顶元素小的时候就出堆
        for (int i = k; i < arr.length; i++) {
            int val = minHeap.peek();
            if(val < arr[i]) {
                minHeap.poll();
                minHeap.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }

代码实现前k个最小元素 :

public class TestDemo<E> {
        //求最小的K个数，通过比较器创建大根堆
        public  int[] smallestK(int[] array, int k) {
            if (k <= 0) {
                return new int[k];
            }
            GreaterIntComp greaterCmp = new GreaterIntComp();
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>(greaterCmp);
            //先将前K个元素，创建大根堆
            for (int i = 0; i < k; i++) {
                maxHeap.offer(array[i]);
            }
//从第K+1个元素开始，每次和堆顶元素比较
            for (int i = k; i < array.length; i++) {
                int top = maxHeap.peek();
                if (array[i] < top) {
                    maxHeap.poll();
                    maxHeap.offer(array[i]);
                }
            }
//取出前K个
            int[] ret = new int[k];
            for (int i = 0; i < k; i++) {
                int val = maxHeap.poll();
                ret[i] = val;
            }
            return ret;
        }
    }
}