写在之前
1.自定义实现采用数组作为内部数据结构
2.内部数组通过grow方法进行扩容,每次只是简单的扩展为原来的2倍
3.集中实现方式的主要区别在于siftDown方法
4.以下给出关键代码,更多详细信息请看附件源码
实现方式一(递归实现)
关键代码:
@Override protected void siftDown(int index) { int len = totalCount - 1; int left = left(index); int right = right(index); if(left > len) { return; } int currentMin = left; if(right <= len && arr[currentMin] > arr[right]) { currentMin = right; } if(arr[currentMin] < arr[index]) { swap(arr, currentMin, index); siftDown(currentMin); } }
实现方式二(循环实现)
关键代码:
@Override protected void siftDown(int index) { int len = totalCount - 1; while(left(index) <= len) { int left = left(index); int right = right(index); if(left > len) { break; } int currentMin = left; if(right <= len && arr[currentMin] > arr[right]) { currentMin = right; } if(arr[currentMin] >= arr[index]) { break; } swap(arr, currentMin, index); index = currentMin; } }
实现方式三(直接构建堆)
关键代码:
@Override protected void siftDown(int index) { int len = totalCount - 1; while(left(index) <= len) { int left = left(index); int right = right(index); if(left > len) { break; } int currentMin = left; if(right <= len && arr[currentMin] > arr[right]) { currentMin = right; } if(arr[currentMin] < arr[index]) { swap(arr, currentMin, index); } //进入下一个非叶子节点 index++; } }
实现方式四(JDK中的实现)
1.siftUp方法:
protected void siftUp(int k, int x) { while (k > 0) { int parent = parent(k); int e = arr[parent]; if (x >= e) break; arr[k] = e; k = parent; } arr[k] = x; }
2.siftDown方法:
/** * 指定index位置的值为x,并为x在堆中找到合适位置 * @param index * @param x */ private void siftDown(int index, int x) { int half = totalCount >>> 1; while (index < half) { int currentMin = left(index); int right = right(index); if (right < totalCount && arr[currentMin] > arr[right]) currentMin = right; if (x <= arr[currentMin]) break; //将index位置设置为最小节点值 arr[index] = arr[currentMin]; //迭代 index = currentMin; } //将最终值放入合适位置 arr[index] = x; }
其他的一下关键方法
1.siftUp方法:
@Override protected void siftUp(int index) { int parent = parent(index); while(index > 0 && arr[index] < arr[parent]) { swap(arr, index, parent); index = parent; parent = parent(index); } }
2.add方法:
@Override public boolean add(int ele) { if(totalCount == arr.length) { //扩容 grow(); } int i = totalCount; arr[i] = ele; if(totalCount == 1) { return true; } //调整元素位置确保为小根堆 siftUp(i); totalCount++; return true; }
3.poll方法:
@Override public int poll() { int result = arr[0]; arr[0] = arr[--totalCount]; siftDown(0); return result; }
5.remove方法:
@Override public int remove(int ele) { //内部数据为空 if(totalCount < 1) { return -1; } //计算元素位置 int index = indexOf(ele); if(index < 0) { return -1; } return removeAt(index); }
6.removeAt方法:
@Override protected int removeAt(int idx) { if(idx < 0 || idx >= totalCount) { return -1; } int result = arr[idx]; //将删除元素与最后一个元素交换位置 if(idx != totalCount -1) { arr[idx] = arr[totalCount - 1]; } //位置交换之后队列长度减一 totalCount--; //如果队列长度大于1,而且删除的元素位置不在队尾则重新调整堆 if(totalCount > 1 && idx != totalCount) { siftDown(idx); } return result; }
相关推荐
几种简单排序之间的比较 小结 问题 实验 编程作业 第4章 栈和队列 不同的结构类型 栈 队列 优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet ...
几种简单排序之间的比较 小结 问题 实验 编程作业 第4章 栈和队列 不同的结构类型 栈 队列 优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet ...
网络爬虫是数据采集的一种方法,实际项目开发中,通过爬虫做数据采集一般只有以下几种情况: 1) 搜索引擎 2) 竞品调研 3) 舆情监控 4) 市场分析 网络爬虫的整体执行流程: 1) 确定一个(多个)种子网页 2) ...
几种简单排序之间的比较 小结 问题 实验 编程作业 第4章 栈和队列 不同的结构类型 栈 队列 优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet 单链表 查找和删除...
几种简单排序之间的比较 小结 问题 实验 编程作业 第4章 栈和队列 不同的结构类型 栈 队列 优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet...
网络爬虫是数据采集的一种方法,实际项目开发中,通过爬虫做数据采集一般只有以下几种情况: 1) 搜索引擎 2) 竞品调研 3) 舆情监控 4) 市场分析 网络爬虫的整体执行流程: 1) 确定一个(多个)种子网页 2) ...
几种简单排序之间的比较 小结 问题 实验 编程作业 第4章 栈和队列 不同的结构类型 栈 队列 优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet...
线程中断/恢复的几种方式 178 创建线程的两种方式 179 线程的控制 180 实例分析 182 内容总结 189 独立实践 190 第十二章:高级I/O流 192 学习目标 192 I/O基础知识 193 字节流 193 字符流 194 节点流 194 过程流 ...
11.2.3优先队列(PriorityQueue)使用示例340 11.2.4哈希集合(HashSet)使用示例343 11.2.5哈希映射类(HashMap)使用示例347 11.2.6有序树(TreeSet)使用示例349 11.2.7有序树映射类(TreeMap)使用示例353 ...
第1篇 Java编程基础 第1章 Java开发环境的搭建(教学视频:9分钟) 2 1.1 理解Java 2 1.2 搭建Java所需环境 3 1.2.1 下载JDK 3 1.2.2 安装JDK 4 1.2.3 配置环境 5 1.2.4 测试JDK配置...
第1篇 Java编程基础 第1章 Java开发环境的搭建(教学视频:9分钟) 2 1.1 理解Java 2 1.2 搭建Java所需环境 3 1.2.1 下载JDK 3 1.2.2 安装JDK 4 1.2.3 配置环境 5 1.2.4 测试JDK配置是否成功 7 实例1 开发第一个Java...
第1篇 Java编程基础 第1章 Java开发环境的搭建(教学视频:9分钟) 2 1.1 理解Java 2 1.2 搭建Java所需环境 3 1.2.1 下载JDK 3 1.2.2 安装JDK 4 1.2.3 配置环境 5 1.2.4 测试JDK配置是否成功 7...
实例141 使用阻塞队列实现线程同步 183 实例142 新建有返回值的线程 184 实例143 使用线程池优化多线程编程 186 实例144 Object类中线程相关的方法 187 实例145 哲学家就餐问题 189 实例146 使用信号量实现线程同步 ...
Java范例开发大全(全书源程序),目录如下: 第1篇 Java编程基础 第1章 Java开发环境的搭建(教学视频:9分钟) 2 1.1 理解Java 2 1.2 搭建Java所需环境 3 1.2.1 下载JDK 3 1.2.2 安装JDK 4 1.2.3 配置环境...
第1篇 Java编程基础 第1章 Java开发环境的搭建(教学视频:9分钟) 2 1.1 理解Java 2 1.2 搭建Java所需环境 3 1.2.1 下载JDK 3 1.2.2 安装JDK 4 1.2.3 配置环境 5 1.2.4 测试JDK配置是否成功 7 实例1 开发第一个Java...
网络爬虫是数据采集的一种方法,实际项目开发中,通过爬虫做数据采集一般有以下几种情况: 1)搜索引擎 2)竞品调研 3)舆情监控 4)市场分析 网络爬虫的整体执行流程 1)确定一个(多个)种子网页 2)进行数据的...