四川简阳建设局招标公告网站,精品课程网站设计报告,淄博网站制作公司定制,承德网站建设服务#x1f525;博客主页#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞#x1f44d;收藏⭐评论✍ 文章目录 1.0 堆的说明 2.0 堆的成员变量及其构造方法 3.0 实现堆的核心方法 3.1 实现堆的核心方法 - 获取堆顶元素 peek() 3.2 实现堆的核心方法 - 下潜 down(int i) 3.3 实… 博客主页 【小扳_-CSDN博客】 ❤感谢大家点赞收藏⭐评论✍ 文章目录 1.0 堆的说明 2.0 堆的成员变量及其构造方法 3.0 实现堆的核心方法 3.1 实现堆的核心方法 - 获取堆顶元素 peek() 3.2 实现堆的核心方法 - 下潜 down(int i) 3.3 实现堆的核心方法 - 交换元素 swap(int i,int j) 3.4 实现堆核心方法 - 删除堆顶元素 poll() 3.5 实现堆的核心方法 - 替换堆顶元素 replace(int i) 3.6 实现堆的核心方法 - 添加元素 offer(int value) 3.7 实现堆的核心方法 - 建堆 heapify() 3.8 实现堆的核心方法完整代码 4.0 TOP - K 问题最小的 K 个数 4.1 实现最小 k 个数的思路 4.2 代码实现最小 k 个数 1.0 堆的说明 堆Heap是一种基于树的数据结构通常用于动态分配内存空间。堆可以被看作是一棵完全二叉树其中每个节点都满足堆的性质即父节点的值大于或等于子节点的值大根堆或父节点的值小于或等于子节点的值小根堆。在堆中根节点的值是最大或最小的因此也被称为最大堆或最小堆。 堆的实现通常使用数组来存储堆中的元素通过计算数组下标来实现节点之间的关系。堆的时间复杂度为 O(log n)其中 n 是堆中元素的数量。 堆的操作包括插入、删除和查找等。插入操作将一个新元素插入到堆中删除操作将堆中的最大或最小元素删除查找操作可以在堆中查找特定元素的位置。 2.0 堆的成员变量及其构造方法 主要的成员变量为int[] arr 数组用来存放元素的容器int size 代表当前的元素个数。 构造方法指定数组大小带参数的构造器、参数为数组的构造器。
代码如下 public class MyHeap {public int[] arr;public int size;public MyHeap(int capacity) {arr new int[capacity];}public MyHeap(int[] arr) {this.arr arr;this.size arr.length;heapify();}} 3.0 实现堆的核心方法 获取堆顶元素、下潜、交换元素、添加元素、替换元素、删除元素、建堆。 3.1 实现堆的核心方法 - 获取堆顶元素 peek() 用数组实现堆在获取堆顶元之前先需要判断该数组是否为空若不为空则直接返回数组索引为 0 的元素若数组为空则返回 0 或者抛出异常也可以。
代码如下 //获取栈顶元素public int peek() {if (isEmpty()) {return -1;}return arr[0];} 3.2 实现堆的核心方法 - 下潜 down(int i) 该方法主要用于删除栈顶元素、替换元素等核心方法。下潜的意思就是将当前的元素所在的位置不符合大顶堆或者小顶堆的规则因此需要向下调整。找到合适的位置来存放当前的元素。 具体下潜的思路 假设需要满足大顶堆的规则 由以上的图来看当前的索引为 0 处的元素 7 小于该左孩子的元素因此当前不满足大顶堆的规则。需要将两者进行交换。 交换的结果为 交换完之后当前索引为 2 处的元素 7 小于该右孩子的元素所以索引 2 与 索引 5 需要继续交换。若当前为 i 该右孩子的索引 left 2 * i 1该左孩子的索引 right 2 * i 2 也可以表示为 right left 1 一开始默认当前的最大元素的索引 max i 接着来判断该左右孩子的元素是否大于当前索引 max 若大于当前索引 max 时需要进行交换 max left 或者 max right 。若不大于当前索引为 max 处的元素则不需要交换。由于每一次都是子问题过程所以可以利用递归来实现当且仅当 max ! i 时说明 max 已经被交换过了需要继续向下递出直到 max i 时结束递出开始回溯。当然这里不需要回带任何值或者变量即该递归函数的返回类型为 viod 。 代码如下 //下潜public void down(int i) {int left 2 * i 1;int right left 1;int max i;if (left size arr[left] arr[max]) {max left;}if (right size arr[right] arr[max]) {max right;}if (max ! i) {//交换swap(i,max);//继续下潜down(max);}} 3.3 实现堆的核心方法 - 交换元素 swap(int i,int j) 交换数组索引中 i 与 j 处的元素。
代码如下 //交换public void swap(int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;} 3.4 实现堆核心方法 - 删除堆顶元素 poll() 具体实现思路为了更高效率的删除堆顶元素后保持原来大顶堆或者小顶堆的规则。 步骤一先将堆顶元素与最后一个元素进行交换。即 arr[0] arr[size - 1] 。 步骤二将 size-- 。 步骤三交换后的堆可能会不满足大顶堆或者小顶堆的规则则需要将堆顶元素进行下潜调整找到合适的位置存放该元素。最后需要返回删除的元素。
代码如下 //删除堆顶元素public int poll() {if (isEmpty()) {return 0;}int t arr[0];arr[0] arr[size - 1];size--;//下潜down(0);return t;} 注意在删除堆顶元素之前需要先判断当前的数组是否为空数组。 同理若需要删除指定堆中的元素索引实现思路是一样的。
代码如下 //指定删除元素public int poll(int i) {if (i size) {return 0;}int temp arr[i];arr[i] arr[size - 1];size--;//下潜down(i);return temp;} 先判断索引是否合法若不合法则返回 0 或者抛出异常也可以。 3.5 实现堆的核心方法 - 替换堆顶元素 replace(int i) 具体思路为先判断该数组是否为空数组若不为空数组则直接替换堆顶元素 arr[0] i之后可能会不满足大顶堆或者小顶堆的规则所以索引为 0 处需要下潜调整找到合适的位置存放元素。
代码实现 //替换堆顶元素public void replace(int i) {if (isEmpty()) {return;}arr[0] i;down(0);} 3.6 实现堆的核心方法 - 添加元素 offer(int value) 具体实现思路先判断当前索引为 i size 处的双亲节点为 j (i - 1) / 2 判断 arr[j] 与 value 的大小若为大顶堆规则则当 arr[j] value 时不需要继续往上走了在 i 处存放 value 即可 arr[i] value 当 arr[j] value 时先将 arr[j] 处的元素存放在 arr[i] 中接着需要继续往上走 i j j (i - 1) / 2 直到 i 0 或者 arr[j] value 时退出循环。在 arr[i] 处存放 value 。
代码如下 //添加元素public boolean offer(int value) {if (isFull()) {return false;}int i size;int j (size - 1) / 2;while (i 0 arr[j] value) {arr[i] arr[j];i j;j (i - 1) / 2;}arr[i] value;size;return true;} 需要注意添加元素前需要先判断该数组是否满了。还有添加完之后需要进行 size 。 3.7 实现堆的核心方法 - 建堆 heapify() 该方法实现的意义若随机给出一个数组需要实现由大顶堆或者小顶堆的结构存放元素。因此就会用到该方法。 实现思路为需要找到最后一个非叶子节点从后往前将当前的元素进行下潜处理即可完成建堆。
代码如下 //建堆public void heapify() {//先找到最后非叶子节点int lastNonLeafNodes size / 2 - 1;for (int i lastNonLeafNodes; i 0 ; i--) {//下潜down(i);}} 3.8 实现堆的核心方法完整代码 public class MyHeap {public int[] arr;public int size;public MyHeap(int capacity) {arr new int[capacity];}public MyHeap(int[] arr) {this.arr arr;this.size arr.length;heapify();}//获取栈顶元素public int peek() {if (isEmpty()) {return -1;}return arr[0];}//删除堆顶元素public int poll() {if (isEmpty()) {return 0;}int t arr[0];arr[0] arr[size - 1];size--;//下潜down(0);return t;}//指定删除元素public int poll(int i) {if (i size) {return 0;}int temp arr[i];arr[i] arr[size - 1];size--;//下潜down(i);return temp;}//替换堆顶元素public void replace(int i) {if (isEmpty()) {return;}arr[0] i;down(0);}//添加元素public boolean offer(int value) {if (isFull()) {return false;}int i size;int j (size - 1) / 2;while (i 0 arr[j] value) {arr[i] arr[j];i j;j (i - 1) / 2;}arr[i] value;size;return true;}//建堆public void heapify() {//先找到最后非叶子节点int lastNonLeafNodes size / 2 - 1;for (int i lastNonLeafNodes; i 0 ; i--) {//下潜down(i);}}//下潜public void down(int i) {int left 2 * i 1;int right left 1;int max i;if (left size arr[left] arr[max]) {max left;}if (right size arr[right] arr[max]) {max right;}if (max ! i) {//交换swap(i,max);//继续下潜down(max);}}//交换public void swap(int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}//判断是否为空数组public boolean isEmpty() {return size 0;}//判断是否为满数组public boolean isFull() {return size arr.length;}
} 4.0 TOP - K 问题最小的 K 个数 题目 设计一个算法找出数组中最小的k个数。以任意顺序返回这 k 个数均可。 示例 输入 arr [1,3,5,7,2,4,6,8], k 4
输出 [1,2,3,4]提示 0 len(arr) 100000 0 k min(100000, len(arr)) OJ 链接 面试题 17.14. 最小K个数 4.1 实现最小 k 个数的思路 具体思路为结合大顶堆的数据结构的特点根节点的元素永远比孩子节点的元素大。先将给定的 arr 数组的前 k 个元素直接通过 heap.offer() 方法添加到大顶堆上然后 arr 数组剩下的元素需要跟堆顶元素相对比若堆顶元素大于 arr[i] 中的元素则需要进行交换将 arr[i] 的元素替换到堆顶接着还不能结束有可能替换完的元素就不符合大顶堆的规则了因此还需要将堆顶元素下潜处理调整找到合适的位置存放该元素若堆顶元素不大于 arr[i] 中的元素则不需要交换。一直将 arr 数组中的元素遍历结束则循环停止。最后堆上存储的 k 个元素就是该数组 arr 中最小的元素了。 4.2 代码实现最小 k 个数 public class Solution {public int[] smallestK(int[] arr, int k) {MaxHeap heap new MaxHeap(k);for(int i 0; i k ; i) {heap.offer(arr[i]);}for(int i k; i arr.length; i) {if(heap.peek() arr[i]) {heap.arr[0] arr[i];heap.down(0);}}return heap.arr;}}//实现一个大顶堆
class MaxHeap {int[] arr;int size;public MaxHeap(int capacity) {arr new int[capacity];}public MaxHeap(int[] smallestK) {this.arr smallestK;this.size smallestK.length;}//插入元素public boolean offer(int value) {if(isFull()) {return false;}int i size;int j (i - 1) / 2;while(i 0 arr[j] value) {arr[i] arr[j];i j;j (i - 1) / 2;}arr[i] value;size;return true;}//删除堆顶元素public int poll() {if(isEmpty()) {return 0;}int ret arr[0];arr[0] arr[size - 1];size--;down(0);return ret;}//下潜public void down(int i) {int left 2 * i 1;int right left 1;int max i;if(left size arr[left] arr[max]) {max left;}if(right size arr[right] arr[max]) {max right;}if(max ! i) {swap(max,i);down(max);}}//交换public void swap(int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}//获取堆顶元素public int peek() {if(isEmpty()) {return 0;}return arr[0];}//判断是否为空public boolean isEmpty() {return size 0;}//判断是否为满public boolean isFull() {return size arr.length;}}
