栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

堆的代码实现、堆排序、TopK问题

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

堆的代码实现、堆排序、TopK问题

目录
    • 堆
      • 一、概念与分类
      • 二、现实生活中的应用
        • 1. 病人手术排期
        • 2. 操作系统的任务调度
      • 三、时间复杂度
      • 四、二叉堆
        • 最大堆
          • 代码实现
        • 最小堆
          • 最小堆转最大堆
        • LeetCode TopK问题
            • leetcode 面试题17.14 最小的k个数
            • leetcode 347 频率最高的k个数
            • leetcode 373 最小的k个数对
        • 堆排序

堆 一、概念与分类

堆即优先级队列。按照优先级的大小动态出队。元素个数动态变化。

堆分为:二叉堆(应用最广泛)、d叉堆、索引堆

二、现实生活中的应用 1. 病人手术排期

病情相同的情况下,先来的病人排在前面,若临时来了个病人病情较重,优先安排手术。而要排手术的病人是不确定的,动态变化的。

相比普通排序,最大的区别是排序的元素个数是确定的,不会发生变化。

2. 操作系统的任务调度

CPU和内存资源有限,当资源不够用时,会先执行优先级较高的任务(通常系统任务的优先级高于普通应用)。而任务数量是不定的,随时有可能开启新任务或关闭旧任务。

三、时间复杂度
入队最大值出队
普通链式队列O(1),一个个尾入O(N),遍历队列,找到最大值
优先级队列(堆)O(logN)O(logN)

O(logN)的时间复杂度通常和“树”结构相关。但并非要实际构造一棵树,而是算法逻辑上的树结构。

归并排序的递归过程也是一棵“递归树”。时间复杂度为O(NlogN)。

四、二叉堆

二叉堆基于完全二叉树实现。只有完全二叉树适用数组存储元素,不会浪费空间用于存储空结点。其他二叉树都使用链式结构。

由于二叉堆使用数组存储,故结点编号可对应数组索引,从0开始。

最大堆

最大堆中只能确定根结点是最大值,子树中并非上层结点就一定大于下层结点。

代码实现

基于动态数组ArrayList实现的最大堆:

//最大堆,基于动态数组ArrayList实现
public class MaxHeap {

    //实际存储堆元素的数组(基于动态数组实现的List接口)
    private List elementData;
    //当前堆中元素个数
    private int size;

    
    public MaxHeap(int size) {
        //使用动态数组存放元素
        elementData = new ArrayList<>(size);
    }

    
    public MaxHeap() {
        this(20);
    }

    
    private int parent(int k) {
        return (k - 1) >> 1;
    }

    
    private int leftChild(int k) {
        return (k << 1) + 1;
    }

    
    private int rightChild(int k) {
        return (k << 1) + 2;
    }

    
    public int getSize() {
        return size;
    }

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

    
    public void add(int val) {
        //往数组末尾添加元素
        elementData.add(val);
        size++;
        //上浮数组尾元素至合适位置,调整为大根堆
        siftUp(size - 1);
    }

    
    private void siftUp(int k) {
        //循环上浮直到无需上浮:1.已经上浮到根结点 2.已满足“当前结点<父结点” 【条件1必须先满足,防止发生数组越界】
        while (k > 0 && elementData.get(k) > elementData.get(parent(k))) {
            //交换当前结点和父结点
            swap(k, parent(k));
            //更新索引,继续上浮
            k = parent(k);
        }
    }

    
    private void swap(int k, int parent) {
        Integer childVal = elementData.get(k);
        Integer parentVal = elementData.get(parent);
        //集合覆盖实现交换
        elementData.set(k, parentVal);
        elementData.set(parent, childVal);
    }

    
    public int extractMax() {
        //堆为空,抛异常
        if(isEmpty()) {
            throw new NoSuchElementException("heap is empty! cannot extract!");
        }
        //堆不为空,堆顶元素即最大值
        int max = elementData.get(0);
        //将堆尾元素顶到堆顶,覆盖堆顶元素(实现删除)
        elementData.set(0, elementData.get(size - 1));
        //删除堆尾元素,否则堆中会出现两个相同元素
        elementData.remove(size - 1);
        size--;
        //从堆顶开始下沉,重新调整为大根堆
        siftDown(0);
        return max;
    }

    
    private void siftDown(int k) {
        //若还存在子树,则循环下沉调整
        while(leftChild(k) < size) {
            //左右子树较大值的索引,初始化左子树为较大值
            int j = leftChild(k);
            //判断右子树是否是最大值:右子树存在 && 右子树大于左子树
            if(j + 1 < size && elementData.get(j + 1) > elementData.get(j)) {
                j++;  //更新较大值索引为右子树
            }
            //判断左右子树的较大值是否比当前树根大
            if(elementData.get(j) > elementData.get(k)) {
                swap(k, j);  //下沉当前树根
                k = j;
            }else {
                break;  //当前树根更大,不下沉
            }
        }
    }

    
    public int peekMax() {
        //查询前先判空
        if(isEmpty()) {
            throw new NoSuchElementException("heap is empty! cannot peek!");
        }
        return elementData.get(0);  //堆顶即最大值
    }

    
    public MaxHeap(int[] arr) {
        //构造新堆,存放元素
        elementData = new ArrayList<>(arr.length);
        for(int i : arr) {
            elementData.add(i);
            size++;
        }
        //从最后一个非叶子结点开始向上循环执行下沉操作,调整为最大堆
        for(int i = parent(size - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    
    public String toString() {
        return elementData.toString();  //List集合已经覆写了toString()方法
    }
}
最小堆

最小堆中只能确定根结点是最小值,子树中并非上层结点就一定小于下层结点。

JDK中的优先级队列PriorityQueue默认采用最小堆实现。

最小堆转最大堆

实现比较器接口Comparator进行倒序比较。

Queue queue = new PriorityQueue<>(new Comparator() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;  //倒序比较
    }
});
LeetCode TopK问题 leetcode 面试题17.14 最小的k个数
public class Interview1714_TopKSmallestNum {

    public int[] smallestK(int[] arr, int k) {
        //返回的结果数组
        int[] ret = new int[k];
        //边界条件
        if(arr.length == 0 || k == 0) {  //防止queue空指针异常
            return ret;  //返回空数组
        }
        //遍历原数组,将前k个数默认存入最大堆
        //JDK默认的优先级队列是基于最小堆的,需改造成最大堆
        Queue queue = new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;  //倒序比较
            }
        });
        //遍历原数组
        for(int i = 0; i < arr.length; i++) {
            //前k个数默认入堆
            if(i < k) {
                queue.offer(arr[i]);
            }else {  //后面的数依次与当前堆顶(最大值)进行比较
                int max = queue.peek();
                //小于堆顶则覆盖堆顶
                if(arr[i] < max) {
                    queue.poll();
                    queue.offer(arr[i]);
                }
                //大于堆顶则说明大于堆中的所有元素,直接跳过
            }
        }
        //此时队列中即保存了k个最小值,依次出队即可
        int i = 0;
        while(!queue.isEmpty()) {
            ret[i++] = queue.poll();
        }
        return ret;
    }
}
leetcode 347 频率最高的k个数
//自定义键值对类
class QueueEntry implements Comparable{
    int key;  //元素值
    int value;  //元素出现的频率

    public QueueEntry(int key, int value) {
        this.key = key;
        this.value = value;
    }
    public int getKey() {
        return key;
    }

    public int getValue() {
        return value;
    }

    //自定义条件比较,频率高的对象大 ==> 正序比较
    @Override
    public int compareTo(QueueEntry o) {
        return this.value - o.value;  //正序比较
    }
}

public class No347_TopKFreqNum {

    public int[] topKFrequent(int[] nums, int k) {
        //返回的结果数组,k个元素值
        int[] ret = new int[k];
        //边界条件
        if(nums.length == 0 || k == 0) {  //防止queue空指针异常
            return ret;  //返回空数组
        }
        //将原数组中的元素及其频率转存到Map集合中 [1,1,1,2,2,3] -> {{1:3},{2:2},{3:1}}
        Map map = new HashMap<>();
        for(int i : nums) {
            if(!map.containsKey(i)) {  //第一次出现的元素直接加入map集合,记录初始频率为1
                map.put(i, 1);
            }else {  //重复出现的元素覆盖频率值
                int freq = map.get(i);  //根据键获取值
                map.put(i, freq + 1);
            }
        }
        //遍历map集合的每个键值对,将频率最高的前k个键值对对象放入优先级队列(最小堆)
        Queue queue = new PriorityQueue<>();  //JDK默认的优先级队列为最小堆
        for(Map.Entry entry : map.entrySet()) {  //将所有键值对提取出来存放到set集合中,用于遍历
            //前k个键值对对象默认入队
            if(queue.size() < k) {
                queue.offer(new QueueEntry(entry.getKey(), entry.getValue()));
            }else {  //后面的键值对对象若大于堆顶,则覆盖堆顶
                if(entry.getValue() > queue.peek().getValue()) {
                    queue.poll();
                    queue.offer(new QueueEntry(entry.getKey(), entry.getValue()));
                }
                //小于堆顶则一定小于堆中所有的键值对对象,直接跳过
            }
        }
        //此时队列中存放的即为前k个频率最高的键值对对象,依次出队,取其键存入结果数组中即可
        int i = 0;
        while (!queue.isEmpty()) {
            ret[i++] = queue.poll().getKey();  //键为元素值
        }
        return ret;
    }
}
leetcode 373 最小的k个数对
public class No373_TopKPairsSumSmallest {

    public List> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //返回的结果二维数组
        List> ret = new ArrayList<>();
        //题目已排除边界情况,无需考虑
        //JDK默认提供的是最小堆,需转换成最大堆  ==> NumPair类需实现倒序的比较器,也确保下方的offer操作正常执行
        Queue queue = new PriorityQueue<>((o1, o2) -> (o2.num1 + o2.num2) - (o1.num1 + o1.num2));  //倒序
        //遍历两个升序数组,仅需分别遍历前k个即可组成包含结果中k个最小数对的所有可能数对,为每个数对创建一个对象
        for(int i = 0; i < Math.min(nums1.length, k); i++) {  //数组长度可能小于k
            for(int j = 0; j < Math.min(nums2.length, k); j++) {
                NumPair numPair = new NumPair(nums1[i], nums2[j]);
                //前k个数对默认入队
                if (queue.size() < k) {
                    queue.offer(numPair);
                } else {  //后面的k个数对小于堆顶则覆盖堆顶,由优先级队列的offer操作自动重新调整为最大堆
                    if ((nums1[i] + nums2[j]) < (queue.peek().num1 + queue.peek().num2)) {
                        queue.poll();  //当前堆顶数对出队
                        queue.offer(numPair);  //新数对入队
                    } else {
                        break;  //找到一个大于堆顶的则后面的数对一定大于堆顶(数组升序),直接break
                    }
                }
            }
        }
        //此时队列中存放的即为前k个和最小的数对对象,依次出队,取其值存入结果数组
        while (!queue.isEmpty()) {
            NumPair numPair = queue.poll();
            List list = new ArrayList<>();
            list.add(numPair.num1);
            list.add(numPair.num2);
            ret.add(list);
        }
        //队列为最大堆,出队的序列为降序,需反转为升序
        Collections.reverse(ret);
        return ret;
    }
}

//数对对象
class NumPair {
    int num1;
    int num2;
    public NumPair(int num1, int num2) {
        this.num1 = num1;
        this.num2 = num2;
    }
}
堆排序
public class HeapSort {

    public static void main(String[] args) {
        int[] arr = new int[] {12,2,4,65,34,7,89,3,0,45,39};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    
    public static void heapSort(int[] arr) {
        // 1.初始化最大堆
        for(int i = (arr.length-1-1)/2; i >= 0; i--) {
            siftDown(arr, i, arr.length);
        }
        // 2.循环交换堆顶和未排序的堆尾元素,每次都让堆顶的最大值到达其排序后的最终位置,并重新调整为最大堆
        for(int i = arr.length-1; i > 0; i--) {  //最后一个元素已为最大值,无需排序 ==> 循环条件 i>0
            //arr[i]即为当前未排序堆中的最后一个元素
            swap(0, i, arr);
            siftDown(arr,0, i);
        }
    }

    
    private static void siftDown(int[] arr, int i, int length) {
        //只要还有子树,就可以循环下沉调整
        while(2 * i + 1 < length) {  //数组从0开始编号:左孩子结点 2*i+1
            // 1.先找出左右孩子中较大者
            int j = 2 * i + 1;  //初始默认左孩子为较大者
            if(j + 1 < length && arr[j+1] > arr[j]) {  //右孩子存在且右孩子较大
                j = j + 1;
            }
            // 2.再比较当前根结点是否小于左右孩子的较大者,小于则下沉,大于则不下沉
            if(arr[i] < arr[j]) {
                swap(i, j, arr);
                i = j;
            }else {
                break;
            }
        }
    }

    private static void swap(int i, int j, int[] arr) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/985108.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号