package com.dataStructure.heap;
import java.util.Arrays;
public class IndexMaxHeap {
// 最大索引堆中的数据
private Integer[] data;
// 最大索引堆中的索引
private int[] indexes;
private int count;
private int capacity;
// 构造函数, 构造一个空堆, 可容纳capacity个元素
public IndexMaxHeap(int capacity) {
this.capacity = capacity;
data = new Integer[capacity + 1];
indexes = new int[capacity + 1];
count = 0;
}
// 返回索引堆中的元素个数
public int size() {
return count;
}
// 返回一个布尔值, 表示索引堆中是否为空
public boolean isEmpty() {
return count == 0;
}
// 向最大索引堆中插入一个新的元素, 新元素的索引为i, 元素为item
// 传入的i对用户而言,是从0索引的
public void insert(int i, Integer integer) {
i += 1;
data[i] = integer;
indexes[count + 1] = i;
count++;
shiftUp(count);
}
// 从最大索引堆中取出堆顶元素, 即索引堆中所存储的最大数据
public Integer extractMax() {
Integer ret = data[indexes[1]];
swapIndexes(1, count);
count--;
shiftDown(1);
return ret;
}
// 从最大索引堆中取出堆顶元素的索引
public int extractMaxIndexes() {
int ret = indexes[1] - 1;
swapIndexes(1, count);
count--;
shiftDown(1);
return ret;
}
// 获取最大索引堆中的堆顶元素
public int getMax() {
return data[indexes[1]];
}
// 获取最大索引堆中的堆顶元素的索引
public int getMaxIndex() {
return indexes[1]-1;
}
// 获取最大索引堆中索引为i的元素
public Integer getInteger(int i) {
return data[i + 1];
}
// 将最大索引堆中索引为i的元素修改为newItem
public void change(int i, Integer newInteger) {
i += 1;
data[i] = newInteger;
// 找到indexes[j] = i, j表示data[i]在堆中的位置
// 之后shiftUp(j), 再shiftDown(j)
for (int j = 1; j <= count; i++) {
if (indexes[j] == i) {
shiftUp(j);
shiftDown(j);
return;
}
}
}
// 交换索引堆中的索引i和j
private void swapIndexes(int i, int j) {
int temp = indexes[i];
indexes[i] = indexes[j];
indexes[j] = temp;
}
//********************
//* 最大索引堆核心辅助函数
//********************
// 索引堆中, 数据之间的比较根据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;
}
}
// 测试索引堆中的索引数组index
// 注意:这个测试在向堆中插入元素以后, 不进行extract操作有效
public boolean testIndexes() {
int[] copyIndexes = new int[count + 1];
for (int i = 0; i <= count; i++) {
copyIndexes[i] = indexes[i];
}
copyIndexes[0] = 0;
Arrays.sort(copyIndexes);
// 在对索引堆中的索引进行排序后, 应该正好是1...count这count个索引
boolean res = true;
for (int i = 1; i <= count; i++) {
if (copyIndexes[i - 1] + 1 != copyIndexes[i]) {
res = false;
break;
}
}
if (!res) {
System.out.println("Error!");
return false;
}
return true;
}
// 测试 IndexMaxHeap
public static void main(String[] args) {
int N = 1000000;
IndexMaxHeap indexMaxHeap = new IndexMaxHeap(N);
for (int i = 0; i < N; i++)
indexMaxHeap.insert(i, (int) (Math.random() * N));
System.out.println(indexMaxHeap.testIndexes());
}
}
在索引中,我们除了data之外,还引入了indexes。data中存放原始数据,indexes中存放的是索引。这里要注意:无论是data数组中的元素,还是indexes数组中的元素,都不构成堆!是谁构成了堆?是下面的这个数组:
data[indexes[1]], data[indexes[2]], data[indexes[3]], ..., data[indexes[n]]
换句话说,我们可以这样理解indexes。将data中的元素组织成一个堆以后,把他们原先对应的序号依次取出来,构成的数组就是索引数组的内容。而data的内容再恢复回去,不要动。在索引堆中,我们可以看到,shiftUp和shiftDown操作只改变索引数组indexes的内容,而不去动data。data就静静地躺在那里,看indexes数组变来变去。最后真正要使用data的时候,只要用indexes相应的元素做索引,指向data就好了。
所以,我们的getMax函数是这样的:
Item getMax(){
assert( count > 0 );
return data[indexes[1]];
}
看,永远取indexes数组第一个元素为索引所对应的那个data,真正改变的是indexes:)