索引堆及其优化(Java 实例代码) 素颜马尾好姑娘i 2023-10-14 15:52 4阅读 0赞 **目录** 索引堆及其优化 一、概念及其介绍 二、适用说明 三、结构图示 四、Java 实例代码 src/runoob/heap/IndexMaxHeap.java 文件代码: -------------------- ## 索引堆及其优化 ## #### 一、概念及其介绍 #### 索引堆是对堆这个数据结构的优化。 索引堆使用了一个新的 int 类型的数组,用于存放索引信息。 相较于堆,优点如下: * 优化了交换元素的消耗。 * 加入的数据位置固定,方便寻找。 #### 二、适用说明 #### 如果堆中存储的元素较大,那么进行交换就要消耗大量的时间,这个时候可以用索引堆的数据结构进行替代,堆中存储的是数组的索引,我们相应操作的是索引。 #### 三、结构图示 #### ![fab3c43601ef3f2d5d3c71becf69b69e.png][] 我们需要对之前堆的代码实现进行改造,换成直接操作索引的思维。首先构造函数添加索引数组属性 indexes。 protected T\[\] data; // 最大索引堆中的数据 protected int\[\] indexes; // 最大索引堆中的索引 protected int count; protected int capacity; 相应构造函数调整为,添加初始化索引数组。 ... public IndexMaxHeap(int capacity)\{ data = (T\[\])new Comparable\[capacity+1\]; indexes = new int\[capacity+1\]; count = 0; this.capacity = capacity; \} ... 调整插入操作,indexes 数组中添加的元素是真实 data 数组的索引 indexes\[count+1\] = i。 ... // 向最大索引堆中插入一个新的元素, 新元素的索引为i, 元素为item // 传入的i对用户而言,是从0索引的 public void insert(int i, Item item)\{ assert count + 1 <= capacity; assert i + 1 >= 1 && i + 1 <= capacity; i += 1; data\[i\] = item; indexes\[count+1\] = i; count ++; shiftUp(count); \} ... 调整 shift up 操作:比较的是 data 数组中父节点数据的大小,所以需要表示为 data\[index\[k/2\]\] < data\[indexs\[k\]\],交换 index 数组的索引,对 data 数组不产生任何变动,shift down 同理。 ... //k是堆的索引 // 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引 private void shiftUp(int k)\{ while( k > 1 && data\[indexes\[k/2\]\].compareTo(data\[indexes\[k\]\]) < 0 )\{ swapIndexes(k, k/2); k /= 2; \} \} ... 从索引堆中取出元素,对大元素为根元素 data\[index\[1\]\] 中的数据,然后再交换索引位置进行 shift down 操作。 ... public T extractMax()\{ assert count > 0; T ret = data\[indexes\[1\]\]; swapIndexes( 1 , count ); count --; shiftDown(1); return ret; \} ... 也可以直接取出最大值的 data 数组索引值 ... // 从最大索引堆中取出堆顶元素的索引 public int extractMaxIndex()\{ assert count > 0; int ret = indexes\[1\] - 1; swapIndexes( 1 , count ); count --; shiftDown(1); return ret; \} ... 修改索引位置数据 ... // 将最大索引堆中索引为i的元素修改为newItem public void change( int i , Item newItem )\{ i += 1; data\[i\] = newItem; // 找到indexes\[j\] = i, j表示data\[i\]在堆中的位置 // 之后shiftUp(j), 再shiftDown(j) for( int j = 1 ; j <= count ; j ++ ) if( indexes\[j\] == i )\{ shiftUp(j); shiftDown(j); return; \} \} ... #### 四、Java 实例代码 #### **源码包下载:**[Download![icon-default.png_t_N6B9][]https://www.runoob.com/wp-content/uploads/2020/09/runoob-algorithm-IndexMaxHeap.zip][Download_icon-default.png_t_N6B9_https_www.runoob.com_wp-content_uploads_2020_09_runoob-algorithm-IndexMaxHeap.zip] ### src/runoob/heap/IndexMaxHeap.java 文件代码: ### package runoob.heap; import java.util.Arrays; /\*\* \* 索引堆 \*/ // 最大索引堆,思路:元素比较的是data数据,元素交换的是索引 public class IndexMaxHeap<T extends Comparable> \{ protected T\[\] data; // 最大索引堆中的数据 protected int\[\] indexes; // 最大索引堆中的索引 protected int count; protected int capacity; // 构造函数, 构造一个空堆, 可容纳capacity个元素 public IndexMaxHeap(int capacity)\{ data = (T\[\])new Comparable\[capacity+1\]; indexes = new int\[capacity+1\]; count = 0; this.capacity = capacity; \} // 返回索引堆中的元素个数 public int size()\{ return count; \} // 返回一个布尔值, 表示索引堆中是否为空 public boolean isEmpty()\{ return count == 0; \} // 向最大索引堆中插入一个新的元素, 新元素的索引为i, 元素为item // 传入的i对用户而言,是从0索引的 public void insert(int i, T item)\{ assert count + 1 <= capacity; assert i + 1 >= 1 && i + 1 <= capacity; i += 1; data\[i\] = item; indexes\[count+1\] = i; count ++; shiftUp(count); \} // 从最大索引堆中取出堆顶元素, 即索引堆中所存储的最大数据 public T extractMax()\{ assert count > 0; T ret = data\[indexes\[1\]\]; swapIndexes( 1 , count ); count --; shiftDown(1); return ret; \} // 从最大索引堆中取出堆顶元素的索引 public int extractMaxIndex()\{ assert count > 0; int ret = indexes\[1\] - 1; swapIndexes( 1 , count ); count --; shiftDown(1); return ret; \} // 获取最大索引堆中的堆顶元素 public T getMax()\{ assert count > 0; return data\[indexes\[1\]\]; \} // 获取最大索引堆中的堆顶元素的索引 public int getMaxIndex()\{ assert count > 0; return indexes\[1\]-1; \} // 获取最大索引堆中索引为i的元素 public T getItem( int i )\{ assert i + 1 >= 1 && i + 1 <= capacity; return data\[i+1\]; \} // 将最大索引堆中索引为i的元素修改为newItem public void change( int i , T newItem )\{ i += 1; data\[i\] = newItem; // 找到indexes\[j\] = i, j表示data\[i\]在堆中的位置 // 之后shiftUp(j), 再shiftDown(j) for( int j = 1 ; j <= count ; j ++ ) if( indexes\[j\] == i )\{ shiftUp(j); shiftDown(j); return; \} \} // 交换索引堆中的索引i和j private void swapIndexes(int i, int j)\{ int t = indexes\[i\]; indexes\[i\] = indexes\[j\]; indexes\[j\] = t; \} //\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* //\* 最大索引堆核心辅助函数 //\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* //k是堆的索引 // 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引 private void shiftUp(int k)\{ while( k > 1 && data\[indexes\[k/2\]\].compareTo(data\[indexes\[k\]\]) < 0 )\{ swapIndexes(k, k/2); k /= 2; \} \} // 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引 private void shiftDown(int k)\{ while( 2\*k <= count )\{ int j = 2\*k; if( j+1 <= count && data\[indexes\[j+1\]\].compareTo(data\[indexes\[j\]\]) > 0 ) j ++; if( data\[indexes\[k\]\].compareTo(data\[indexes\[j\]\]) >= 0 ) break; swapIndexes(k, j); k = j; \} \} // 测试 IndexMaxHeap public static void main(String\[\] args) \{ int N = 1000000; IndexMaxHeap<Integer> indexMaxHeap = new IndexMaxHeap<Integer>(N); for( int i = 0 ; i < N ; i ++ ) indexMaxHeap.insert( i , (int)(Math.random()\*N) ); \} \} 上述修改索引位置在查找索引位置我们使用了遍历,效率不高。我们还可以再优化一遍,维护一组 reverse\[i\] 数组,表示索引 i 在 indexes(堆) 中的位置,把查找的时间复杂度降为 O(1)。 ![ae969500beda42b928e78668116733d3.png][] 有如下性质: indexes[i] = j reverse[j] = i indexes[reverse[i]] = i reverse[indexes[i]] = i [fab3c43601ef3f2d5d3c71becf69b69e.png]: https://img-blog.csdnimg.cn/img_convert/fab3c43601ef3f2d5d3c71becf69b69e.png [icon-default.png_t_N6B9]: https://csdnimg.cn/release/blog_editor_html/release2.3.5/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N6B9 [Download_icon-default.png_t_N6B9_https_www.runoob.com_wp-content_uploads_2020_09_runoob-algorithm-IndexMaxHeap.zip]: https://www.runoob.com/wp-content/uploads/2020/09/runoob-algorithm-IndexMaxHeap.zip [ae969500beda42b928e78668116733d3.png]: https://img-blog.csdnimg.cn/img_convert/ae969500beda42b928e78668116733d3.png
相关 代码优化挑战:减少Java代码冗余实例 在Java编程中,冗余代码通常意味着重复的工作或者逻辑。优化的目标是消除这些重复,提高代码的可读性和维护性。以下是一些减少Java代码冗余的例子: 1. **使用方法和变量* 小灰灰/ 2024年09月10日 09:24/ 0 赞/ 19 阅读
相关 索引堆及其优化 一、概念及其介绍 索引堆是对堆这个数据结构的优化。 索引堆使用了一个新的 int 类型的数组,用于存放索引信息。 相较于堆,优点如下: 优化了交换元素的消耗。 系统管理员/ 2024年03月16日 20:54/ 0 赞/ 46 阅读
相关 索引堆及其优化(Java 实例代码) 目录 索引堆及其优化 一、概念及其介绍 二、适用说明 三、结构图示 四、Java 实例代码 src/runoob/heap/IndexMaxHeap.java 文件 素颜马尾好姑娘i/ 2023年10月14日 15:52/ 0 赞/ 5 阅读
相关 基础堆排序(Java 实例代码) 目录 基础堆排序 一、概念及其介绍 二、适用说明 三、过程图示 四、Java 实例代码 src/runoob/heap/Heapify.java 文件代码: -- 秒速五厘米/ 2023年10月14日 15:52/ 0 赞/ 5 阅读
相关 优化堆排序(Java 实例代码) 目录 优化堆排序 Java 实例代码 src/runoob/heap/HeapSort.java 文件代码: -------------------- 优化堆排序 桃扇骨/ 2023年10月14日 15:52/ 0 赞/ 2 阅读
相关 堆的 shift down(Java 实例代码) 目录 堆的 shift down 四、Java 实例代码 src/runoob/heap/HeapShiftDown.java 文件代码: -------------- - 日理万妓/ 2023年10月14日 15:52/ 0 赞/ 3 阅读
相关 堆的基本存储(Java 实例代码) 堆的基本存储 一、概念及其介绍 堆(Heap)是计算机科学中一类特殊的数据结构的统称。 堆通常是一个可以被看做一棵完全二叉树的数组对象。 堆满足下列性质 桃扇骨/ 2023年10月14日 15:51/ 0 赞/ 7 阅读
相关 索引堆 将数组的索引重新按优先级建立新的索引;数组的索引代表从小到大的顺序,而新索引里面对应着堆的不同位置对应的数组的位置。 如果想更改数组中的某个元素,要维护index数组(堆) ╰+攻爆jí腚メ/ 2023年08月17日 17:10/ 0 赞/ 60 阅读
相关 MySQL索引优化实例说明 下面分别创建三张表,并分别插入1W条简单的数据用来测试,详情如下: \[1\] test\_a 有主键但无索引 CREATE TABLE \`test\_a\` ( 蔚落/ 2022年06月15日 23:57/ 0 赞/ 137 阅读
还没有评论,来说两句吧...