一条龙建站多少钱,wordpress主题很慢,免费php网站源码,烟台 网站建设本文着重在于讲解用 “堆实现优先级队列” 以及优先级队列的应用#xff0c;在本文所举的例子中#xff0c;可能使用优先级队列来解并不是最优解法#xff0c;但是正如我所说的#xff1a;本文着重在于讲解“堆实现优先级队列” 堆实现优先级队列
堆的主要应用有两个… 本文着重在于讲解用 “堆实现优先级队列” 以及优先级队列的应用在本文所举的例子中可能使用优先级队列来解并不是最优解法但是正如我所说的本文着重在于讲解“堆实现优先级队列” 堆实现优先级队列
堆的主要应用有两个一个是排序方法[堆排序]一个是数据结构 [优先级队列]。
我们会发现人们总是把二叉堆画成一棵二叉树。其实二叉堆在逻辑上就是一种特殊的二叉树只不过存储在数组里。
比如 arr 是一个字符数组注意数组的第一个索引 0 空着不用 为什么索引 0 空着不用
为了方便计算父节点和子节点的索引通常会将数组的第一个元素存储在索引1的位置上而不是索引0。这样可以通过简单的数学计算得到父节点和子节点的索引而无需进行额外的操作。
具体来说在该代码中
根据完全二叉树的性质如果某个节点的索引为i则其左子节点的索引为2i右子节点的索引为2i 1。
如果索引从1开始则根节点的索引为1其左子节点的索引为2右子节点的索引为3。
如果索引从0开始则根节点的索引为0其左子节点的索引为1右子节点的索引为2。
因此为了避免对索引的调整和计算通常会将数组的第一个元素放在索引1的位置上并从索引1开始使用。这也是为什么在这段代码中索引0不被使用的原因。
请注意这种索引方式只是约定俗成的一种做法并非固定规定。在某些情况下也可以使用索引从0开始的方式实现堆或优先队列。这取决于具体的实现和需求。
构建优先级队列
可以使用 最大堆/最小堆 来构建优先级队列当插入或者删除元素的时候元素会自动排序这底层的原理就是二叉堆的操作。
当我们使用一个最大堆来实现一个优先级队列时堆顶元素总是数组中的最大值。这背后就是由[上浮] 和 [下沉] 两个操作来维护堆结构的。
维护堆结构的操作——swim和sink
我们要讲的是最大堆每个节点都比它的两个子节点大但是在插入元素和删除元素时难免破坏堆的性质这就需要通过这两个操作来恢复堆的性质了。
对于最大堆会破坏堆性质的有两种情况
1、如果某个节点 A 比它的子节点中的一个小那么 A 就不配做父节点应该下去下面那个更大的节点上来做父节点这就是对 A 进行下沉。
2、如果某个节点 A 比它的父节点大那么 A 不应该做子节点应该把父节点换下来自己去做父节点这就是对 A 的上浮。
当然错位的节点 A 可能要上浮或下沉很多次才能到达正确的位置恢复堆的性质。所以代码中肯定有一个 while 循环。
上浮操作的实现
private void swim(int x) {// 索引 1 是堆顶//判断x不是堆顶元素且x大于其父结点while (x 1 less(parent(x), x)) {// 交换x的父结点与x下标元素swap(parent(x), x);//将父节点的索引给x指针指向xx parent(x);}}
下沉操作的实现
private void sink(int x) {// size 是堆的最后一个索引//判断当x的左节点不是堆底元素时while (left(x) size) {// 先假设左边节点较大int max left(x);// 如果右边节点存在比一下大小//判断右节点不是堆底元素且右节点值大于max的值if (right(x) size less(max, right(x)))max right(x);// 结点 x 比俩孩子都大就不必下沉了if (less(max, x)) break;// 否则不符合最大堆的结构下沉 x 结点swap(x, max);x max;}}
数据结构的基本操作——增删查改
增加操作
将元素插到堆的底部然后上浮到对应位置
public void insert(Key e) {size;// 先把新元素加到最后pq[size] e;// 然后让它上浮到正确的位置swim(size);}
删除操作 将要删除的元素与堆底元素对调然后删除堆底元素。最后维护堆结构
public Key delMax() {// 最大堆的堆顶就是最大元素Key max pq[1];// 把这个最大元素换到最后删除之swap(1, size);pq[size] null;size--;// 让 pq[1] 下沉到正确位置sink(1);return max;}
查看操作 查看最大值直接返回堆顶元素即可
public Key max() {return pq[1];}
整体代码 public class MaxPQKey extends ComparableKey {/*完全二叉树中的索引下标是可以计算出来的*/// 父节点的索引int parent(int root) {return root / 2;}// 左孩子的索引int left(int root) {return root * 2;}// 右孩子的索引int right(int root) {return root * 2 1;}// 存储元素的数组private Key[] pq;// 当前 Priority Queue 中的元素个数private int size 0;public MaxPQ(int cap) {// 索引 0 不用所以多分配一个空间pq (Key[]) new Comparable[cap 1];}/* 返回当前队列中最大元素 */public Key max() {return pq[1];}/* 插入元素 e */public void insert(Key e) {size;// 先把新元素加到最后pq[size] e;// 然后让它上浮到正确的位置swim(size);}/* 删除并返回当前队列中最大元素 */public Key delMax() {// 最大堆的堆顶就是最大元素Key max pq[1];// 把这个最大元素换到最后删除之swap(1, size);pq[size] null;size--;// 让 pq[1] 下沉到正确位置sink(1);return max;}/* 上浮第 x 个元素以维护最大堆性质 */private void swim(int x) {// 如果浮到堆顶就不能再上浮了//因为是从索引1开始的所以索引1是堆顶//判断当x不是堆顶且x的父结点小于x时while (x 1 less(parent(x), x)) {// 如果第 x 个元素比上层大// 交换数组下标元素swap(parent(x), x);x parent(x);}}/* 下沉第 x 个元素以维护最大堆性质 */private void sink(int x) {// 如果沉到堆底就沉不下去了while (left(x) size) {// 先假设左边节点较大int max left(x);// 如果右边节点存在比一下大小if (right(x) size less(max, right(x)))max right(x);// 结点 x 比俩孩子都大就不必下沉了if (less(max, x)) break;// 否则不符合最大堆的结构下沉 x 结点swap(x, max);x max;}}/* 交换数组的两个元素 */private void swap(int i, int j) {Key temp pq[i];pq[i] pq[j];pq[j] temp;}/* pq[i] 是否比 pq[j] 小 */private boolean less(int i, int j) {return pq[i].compareTo(pq[j]) 0;}
}附注1对Key extends ComparableKey的解释 Key extends ComparableKey是Java的泛型语法。它指示了MaxPQ类使用一个类型参数Key并且要求这个类型Key必须实现了ComparableKey接口。 ComparableKey接口是Java中定义的一个泛型接口用于比较两个对象的顺序。它要求实现类具有比较自身与其他对象的能力并返回一个整数值表示它们的相对顺序。 通过实现Comparable接口我们可以在堆和优先级队列中比较元素的大小以维护它们的排序规则。 在这段代码中Key作为泛型参数限制了存储在pq数组中的元素类型必须实现Comparable接口以便能够进行比较操作例如使用compareTo方法。这样做可以确保我们能够正确地进行插入、删除和获取最大元素等操作使得堆和优先级队列能够按照特定的顺序进行排序和处理。
附注2对“pq (Key[]) new Comparable[cap 1]”的解释 在这段代码中pq (Key[]) new Comparable[cap 1];是用来创建一个泛型数组的操作。 首先我们需要了解在Java中创建泛型数组的限制。由于Java的类型擦除机制无法直接创建一个具体类型的泛型数组。 因此我们只能通过创建一个非泛型数组然后将其转换为泛型数组。 在这段代码中new Comparable[cap 1]创建了一个长度为cap 1的非泛型数组 并且元素的类型是Comparable接口。这个数组在内存中被分配了空间。 然后(Key[])表示进行了一个类型转换。 因为我们知道该数组是要存储Key类型的元素所以我们将其强制转换为泛型数组类型Key[]。 最后将转换后的泛型数组赋值给变量pq使得pq引用这个泛型数组。 需要注意的是在进行强制类型转换时存在一定的风险。 如果实际存储在数组中的元素类型不符合泛型参数Key的约束条件可能会导致运行时错误。 因此在使用该代码时应确保泛型参数和实际存储的元素类型是匹配的。*/
优先级队列的应用
力扣215. 数组中的第K个最大元素
思路
使用数组构造一个最大堆然后选出第k大的元素
构建最大堆 // 构建最大堆public void buildMaxHeap(int[] a, int heapSize) {for (int i heapSize / 2; i 0; --i) {maxHeapify(a, i, heapSize); // 对每个非叶子节点进行调整使其满足最大堆的性质}}// 调整以i为根节点的子树使其满足最大堆的性质public void maxHeapify(int[] a, int i, int heapSize) {//计算左右节点的下标int left i * 2 1, right i * 2 2, largest i;// 下沉操作比较节点i与其左右子节点的值找到最大值// 先与左节点对比if (left heapSize a[left] a[largest]) {largest left;}// 再与右节点对比if (right heapSize a[right] a[largest]) {largest right;}if (largest ! i) {swap(a, i, largest); // 将节点i与最大值节点交换位置maxHeapify(a, largest, heapSize); // 继续向下调整以保持最大堆的性质}}// 交换数组中两个元素的位置public void swap(int[] a, int i, int j) {int temp a[i];a[i] a[j];a[j] temp;}
问题1 “for (int i heapSize / 2; i 0; --i)”是什么意思
在构建最大堆时我们只需要对非叶子节点进行调整而不需要对叶子节点进行调整。这是因为堆的性质决定了一个完全二叉树的叶子节点已经满足最大堆的条件即叶子节点的值不会比其父节点更大。
考虑到完全二叉树的特点具有n/2个节点是非叶子节点其中n是堆中元素的总数。比如下标为i的元素其左节点为 2i右节点为 2i1所以对n个节点来说只能有n/2个节点是非叶子节点。
所以我们可以从最后一个非叶子节点索引为n/2 - 1开始向前逐个调用maxHeapify方法将每个节点及其子树调整为最大堆。
由于最大堆的性质要求父节点的值大于或等于其子节点的值通过逐层向上调整非叶子节点我们能够确保整个堆都满足最大堆的要求。
因此在buildMaxHeap方法中我们只对非叶子节点进行调整以节省时间 选出第k大的元素
选出第k大的元素的方法是取出堆顶的元素将其与堆底元素交换然后缩小堆重新维护堆结构。就相当于把堆顶的最大元素删除了。
正数第k个元素就是倒数的第 length - k 1个元素所以我们将后面length - k 1个元素与堆顶元素交换即可
public int findKthLargest(int[] nums, int k) {int heapSize nums.length;buildMaxHeap(nums, heapSize); // 构建最大堆for (int i nums.length - 1; i nums.length - k 1; --i) {swap(nums, 0, i); // 将堆顶元素与当前未排序部分的最后一个元素交换--heapSize; // 缩小堆的大小maxHeapify(nums, 0, heapSize); // 调整堆使其继续满足最大堆的性质}return nums[0]; // 返回第k个最大元素堆顶元素}
整体代码 class Solution {public int findKthLargest(int[] nums, int k) {int heapSize nums.length;buildMaxHeap(nums, heapSize); // 构建最大堆for (int i nums.length - 1; i nums.length - k 1; --i) {swap(nums, 0, i); // 将堆顶元素与当前未排序部分的最后一个元素交换--heapSize; // 缩小堆的大小maxHeapify(nums, 0, heapSize); // 调整堆使其继续满足最大堆的性质}return nums[0]; // 返回第k个最大元素堆顶元素}// 构建最大堆public void buildMaxHeap(int[] a, int heapSize) {for (int i heapSize / 2; i 0; --i) {maxHeapify(a, i, heapSize); // 对每个非叶子节点进行调整使其满足最大堆的性质}}// 调整以i为根节点的子树使其满足最大堆的性质public void maxHeapify(int[] a, int i, int heapSize) {//计算左右节点的下标int left i * 2 1, right i * 2 2, largest i;// 下沉操作比较节点i与其左右子节点的值找到最大值// 先与左节点对比if (left heapSize a[left] a[largest]) {largest left;}// 再与右节点对比if (right heapSize a[right] a[largest]) {largest right;}if (largest ! i) {swap(a, i, largest); // 将节点i与最大值节点交换位置maxHeapify(a, largest, heapSize); // 继续向下调整以保持最大堆的性质}}// 交换数组中两个元素的位置public void swap(int[] a, int i, int j) {int temp a[i];a[i] a[j];a[j] temp;}
}
力扣347. 前 K 个高频元素
使用哈希表记录每个元素与其出现次数的映射关系
构建一个大小为k的小根堆如果不足k个元素就直接将当前数字加入到堆中
否则判断堆中的最小值是否小于当前数字的出现次数如果堆中的最小值小于当前数字出现次数说明目前的堆顶元素不在前k个高频元素中将其弹出并将当前数字加入到堆中
import java.util.*;class Solution {public int[] topKFrequent(int[] nums, int k) {// 统计每个数字出现的次数MapInteger, Integer counter new HashMap();for (int num : nums) {counter.put(num, counter.getOrDefault(num, 0) 1);}// 定义小根堆根据数字频率自小到大排序QueueInteger pq new PriorityQueue((v1, v2) - counter.get(v1) - counter.get(v2));// 遍历数组维护一个大小为 k 的小根堆// 不足 k 个直接将当前数字加入到堆中否则判断堆中的最小次数是否小于当前数字的出现次数// 若是则删掉堆中出现次数最少的一个数字将当前数字加入堆中。for (int num : counter.keySet()) {if (pq.size() k) {pq.offer(num);} else if (counter.get(pq.peek()) counter.get(num)) {pq.poll();pq.offer(num);}}// 构造返回结果int[] res new int[k];int idx 0;for (int num : pq) {res[idx] num;}return res;}
}
