基础知识(青铜挑战)
-
堆的概念:堆是一种数据结构,按照完全二叉树的存储顺序,将数据存储在一个一维数组中
-
大顶堆:任意节点值均大于它的左右节点值
-
小顶堆:任意节点值均大于它的左右节点值
-
-
堆的构造过程:按照层次将所有元素一次添入二叉树中,再不断调整,最终使其符合堆结构
-
堆中插入元素:确认插入位置能够保持原二叉树为完全二叉树,再自底向上调整,保证每一层的子树都符合堆结构
-
堆中删除元素:一般都是删除堆顶元素,将堆顶元素与二叉树最后一个元素对调,删除堆顶元素后,再依次调整每一层的各子树
实战训练(白银挑战)
数组中查找第K大的元素
-
这个问题很重要很经典,解决方法也有多种,我们提三个:选择法、快排、堆排序
-
堆排序:
-
我们需要在数组中查找第K大的元素,就创建一个大小为K的小顶堆
-
堆满后,只有比堆顶元素小的元素,才可以插入堆中;新插入的元素先覆盖堆顶元素后,再调整
-
将数组序列依次插入堆中,每插入一个元素,就调整堆使之符合堆的结构
-
全部序列入堆完毕后,堆顶元素就是要查找的第K大的元素了
-
-
具体代码如下:
public static int findKthLargest(int[] nums, int k) {if (k > nums.length) {return -1;}int len = nums.length;// 使用一个含有 k 个元素的最小堆PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);for (int i = 0; i < k; i++) {minHeap.add(nums[i]);}for (int i = k; i < len; i++) {// 看一眼,不拿出,因为有可能没有必要替换Integer topEle = minHeap.peek();// 只要当前遍历的元素比堆顶元素大,堆顶弹出,遍历的元素进去if (nums[i] > topEle) {minHeap.poll();minHeap.offer(nums[i]);}}return minHeap.peek();}
堆排序
-
堆排序是什么原理呢?
-
构造大顶堆,依次取出堆顶元素;每取出一个堆顶元素后,重新调整堆,这样得到的序列就是从大到小排序的(降序排序)
-
小顶堆同理,得到的序列就是从小到大排序的(升序排序)
-
升序用小,降序用大 (2023/09/30晚)