最大索引堆（IndexMaxHeap）
一、概念及其介绍
索引堆是对堆这种数据结构的优化，是利用真正元素的索引值来组成一个堆，可以映射出一个最大堆或者最小堆，索引堆可分为最大索引堆 (IndexMaxHeap) 和最小索引堆 (IndexMinHeap)
为什么要索引堆：
当我们在使用堆这个数据结构的时候，需要对堆进行一系列的操作，如插入，取出等操作，我们会不断的改变相应数据的位置，此时当数据较大的时候，如每个堆中的数据都是一个较大文本等，在交换位置是就会对计算机有较大消耗；所以这里我们引入索引堆，索引堆是根据比较真正数据，但改变位置的是对应数据索引的位置真正操作的是对应数据的索引，真正数据位置不变，其优点总结如下：
- 优化了交换元素的消耗。
- 加入的数据位置固定，方便寻找。
二、结构图示实现分析
实现思想: 比较data数据,交换的是索引元素，首先构造函数添加索引数组属性 indexes
private T[] data; // 最大索引堆中的数据
private int[] indexes; // 最大索引堆中的索引
private int count; // 索引堆中元素个数
private int capacity; // 表示堆的容量
相应构造函数调整为，添加初始化索引数组
public IndexMaxHeap(int capacity) {
data = (T[]) new Comparable[capacity + 1];
indexes = new int[capacity + 1];
count = 0;
this.capacity = capacity;
}
我们要对最大索引堆进行插入操作，这里我们定义一个 insert () 函数
public void insert(int i, T item) {
assert count + 1 <= capacity;
assert i + 1 >= 1 && i + 1 <= capacity;
i += 1;
data[i] = item;
// 调整插入操作，indexes 数组中添加的元素是真实 data 数组的索引 indexes [count+1] = i
indexes[count + 1] = i;
count++;
shiftUp(count);
}
调整 shift up 操作：比较的是 data 数组中父节点数据的大小，所以需要表示为 data[index[k/2]] < data[indexs[k]]，交换 index 数组的索引，对 data 数组不产生任何变动，shift down 同理。
private void shiftUp(int k) {
while (k > 1 && data[indexes[k / 2]].compareTo(data[indexes[k]]) < 0) {
swapIndexes(k, k / 2); // 交换索引
k /= 2;
}
}
我们要对最大索引堆中元素进行取出，其逻辑和堆一样，我们也需要将 data [1] 改为 data [indexes [1]];（ 与 shiftUp () 同理 ）
public T extractMax() {
assert count > 0;
T ret = data[indexes[1]];
swapIndexes(1, count);
count--;
shiftDown(1);
return ret;
}
下面来实现 shiftDown ()，其数组索引方法和 shiftUp () 同理
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;
}
}
在索引堆中还有一个重要的功能，就是我们需要更新索引堆里的元素，传入需要改变值对应的索引 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;
}
}
三、完整代码示例
https://github.com/perkinls/java-summary/
关注公众号 ，专注于java大数据领域离线、实时技术干货定期分享！如有问题随时沟通交流！ www.lllpan.top
