目录
实现最大索引堆
1、 实现
package com.yunche.datastructure;/** * @ClassName: IndexMaxHeap * @Description: 最大索引堆：利用数据的索引构建成最大索引堆，使构建最大堆时只需 * 移动索引, 而不需移动数据元素本身。 * 注意：当最大索引堆构建完成后，最大数据元素的索引位于最大索引堆的堆顶，但其索引不一定是最大的。 * @author: yunche * @date: 2018/12/25 */public class IndexMaxHeap{ /** * 存储索引堆中索引指向的元素 */ private T[] data; /** * 堆中元素的个数 */ private int count; /** * 堆中最大容量 */ private int capacity; /** * 存储索引堆中的索引 */ private int[] indexes; /** * 构造一个空堆，最多容纳capacity个元素 * * @param capacity */ public IndexMaxHeap(int capacity) { this.capacity = capacity; count = 0; //数组从索引为1的位置开始存储元素 indexes = new int[capacity + 1]; data = (T[]) new Comparable[capacity + 1]; } /** * 返回堆中元素个数 * * @return */ public int size() { return count; } /** * 返回堆中是否为空 * * @return */ public boolean isEmpty() { return count == 0; } /** * 向最大索引堆中插入一个新元素，索引为i，元素数据为item * 用户传入的索引i是从0开始的 * * @param item */ public void insert(int i, T item) { if (count == capacity) { capacity = capacity << 1; T[] tem = (T[]) new Comparable[capacity + 1]; int[] t_indexes = new int[capacity + 1]; for (int k = 1; k <= count; k++) { t_indexes[k] = indexes[k]; tem[t_indexes[k]] = data[indexes[k]]; } data = tem; indexes = t_indexes; } if (i + 1 < 1 || i + 1 > capacity) { System.out.println("索引 " + i + " 无效"); return; } //调整索引值，使它从1开始 i += 1; indexes[++count] = i; data[i] = item; shiftUp(count); } /** * 从最大索引堆中取出最大元素，即堆顶元素 * * @return 返回最大元素 */ public T extractMax() { if (count == 0) { return null; } T ret = data[indexes[1]]; data[indexes[1]] = null; swapIndexes(1, count--); shiftDown(1); return ret; } /** * 获取最大索引堆中的堆顶元素 * * @return */ public T getMax() { if (count == 0) { return null; } return data[indexes[1]]; } /** * 获取最大索引堆中的堆顶元素的索引 * * @return */ public int getMaxIndex() { if (count == 0) { return -1; } return indexes[1] - 1; } /** * 获取最大索引堆中索引为i的元素 * * @param i * @return */ public T getItem(int i) { if (i + 1 < 1 || i + 1 > capacity) { return null; } return data[i + 1]; } /** * 将最大索引堆中索引为i的元素修改为t * * @param i * @param t */ public void change(int i, T t) { i += 1; data[i] = t; for (int j = 1; j <= count; j++) { if (indexes[j] == i) { shiftUp(j); shiftDown(j); return; } } } /** * 在最大索引堆中，数据之间的比较是根据data的大小，但实际移动的是索引 * * @param k 索引 */ private void shiftUp(int k) { while (k > 1 && less(data[indexes[k >> 1]], data[indexes[k]])) { swapIndexes(k >> 1, k); k >>= 1; } } /** * 在最大索引堆中，数据之间的比较是根据data的大小，但实际移动的是索引 * * @param k */ private void shiftDown(int k) { //边界：确保至少有一个孩子 while (2 * k <= count) { // 在此轮循环中,data[k]和data[j]交换位置 int j = 2 * k; if (j + 1 <= count && less(data[indexes[j]], data[indexes[j + 1]])) { j++; } // data[j] 是 data[2*k]和data[2*k+1]中的最大值 if (!less(data[indexes[k]], data[indexes[j]])) { break; } swapIndexes(k, j); k = j; } } /** * 交换堆中索引为i和j的两个元素 * * @param i * @param j */ private void swapIndexes(int i, int j) { int t = indexes[i]; indexes[i] = indexes[j]; indexes[j] = t; } private boolean less(T t1, T t2) { return t1.compareTo(t2) < 0; } public static void main(String[] args) { IndexMaxHeap indexMaxHeap = new IndexMaxHeap(10); indexMaxHeap.insert(0, 12); indexMaxHeap.insert(1, 4); indexMaxHeap.insert(2, 32); indexMaxHeap.insert(4,13); indexMaxHeap.insert(3, 21); while (!indexMaxHeap.isEmpty()) { System.out.println("索引：" + indexMaxHeap.getMaxIndex() + " 值为：" + indexMaxHeap.extractMax()); } }}
2、 优化
添加了 reverse数组，将 change 操作的时间复杂度从 O（n）降为了 O（1）并添加了 contain 方法用来判断用户输入的索引是否存在。
reverse[i] 表示索引i在indexes(堆)中的位置
所以，如果 indexes[i] = j， reverse[j] = i，那么
indexes[reverse[i]] =i, reverse[indexes[i]] = i
证明indexes[reverse[i]] =i：若reverse[i] = x, 即等价于证明indexes[x] = i
根据条件，得证。
package com.yunche.datastructure;/** * @ClassName: IndexMaxHeap * @Description: 最大索引堆：利用数据的索引构建成最大索引堆，使构建最大堆时只需 * 移动索引, 而不需移动数据元素本身。 * 注意：当最大索引堆构建完成后，最大数据元素的索引位于最大索引堆的堆顶，但其索引不一定是最大的。 * @author: yunche * @date: 2018/12/25 */public class IndexMaxHeap{ /** * 存储索引堆中索引指向的元素 */ private T[] data; /** * 堆中元素的个数 */ private int count; /** * 堆中最大容量 */ private int capacity; /** * 存储索引堆中的索引 */ private int[] indexes; /** * 存储指定索引在堆中的位置 */ private int[] reverse; /** * 构造一个空堆，最多容纳capacity个元素 * * @param capacity */ public IndexMaxHeap(int capacity) { this.capacity = capacity; count = 0; //数组从索引为1的位置开始存储元素 indexes = new int[capacity + 1]; reverse = new int[capacity + 1]; data = (T[]) new Comparable[capacity + 1]; } /** * 判读索引堆中是否存在该索引 * * @param i * @return */ public boolean contain(int i) { if (i + 1 < 1 || i + 1 > capacity) { System.out.println("索引 " + i + " 无效"); return false; } return reverse[i + 1] != 0; } /** * 返回堆中元素个数 * * @return */ public int size() { return count; } /** * 返回堆中是否为空 * * @return */ public boolean isEmpty() { return count == 0; } /** * 向最大索引堆中插入一个新元素，索引为i，元素数据为item * 用户传入的索引i是从0开始的 * * @param item */ public void insert(int i, T item) { if (count == capacity) { capacity = capacity << 1; T[] tem = (T[]) new Comparable[capacity + 1]; int[] t_indexes = new int[capacity + 1]; int[] t_reverse = new int[capacity + 1]; for (int k = 1; k <= count; k++) { t_indexes[k] = indexes[k]; t_reverse[k] = reverse[k]; tem[t_indexes[k]] = data[indexes[k]]; } data = tem; indexes = t_indexes; reverse = t_reverse; } if (contain(i)) { System.out.println("索引已存在！"); return; } //调整索引值，使它从1开始 i += 1; indexes[++count] = i; reverse[i] = count; data[i] = item; shiftUp(count); } /** * 从最大索引堆中取出最大元素，即堆顶元素 * * @return 返回最大元素 */ public T extractMax() { if (count == 0) { return null; } T ret = data[indexes[1]]; data[indexes[1]] = null; swapIndexes(1, count); reverse[indexes[count--]] = 0; shiftDown(1); return ret; } /** * 获取最大索引堆中的堆顶元素 * * @return */ public T getMax() { if (count == 0) { return null; } return data[indexes[1]]; } /** * 获取最大索引堆中的堆顶元素的索引 * * @return */ public int getMaxIndex() { if (count == 0) { return -1; } return indexes[1] - 1; } /** * 获取最大索引堆中索引为i的元素 * * @param i * @return */ public T getItem(int i) { if (!contain(i)) { return null; } return data[i + 1]; } /** * 将最大索引堆中索引为i的元素修改为t * * @param i * @param t */ public void change(int i, T t) { if (!contain(i)) { System.out.println("索引有误"); return; } i += 1; data[i] = t;// for (int j = 1; j <= count; j++) {// if (indexes[j] == i) {// shiftUp(j);// shiftDown(j);// return;// }// } //通过reverse直接定位索引i在indexes中的位置 shiftUp(reverse[i]); shiftDown(reverse[i]); } /** * 在最大索引堆中，数据之间的比较是根据data的大小，但实际移动的是索引 * * @param k 索引 */ private void shiftUp(int k) { while (k > 1 && less(data[indexes[k >> 1]], data[indexes[k]])) { swapIndexes(k >> 1, k); k >>= 1; } } /** * 在最大索引堆中，数据之间的比较是根据data的大小，但实际移动的是索引 * * @param k */ private void shiftDown(int k) { //边界：确保至少有一个孩子 while (2 * k <= count) { // 在此轮循环中,data[k]和data[j]交换位置 int j = 2 * k; if (j + 1 <= count && less(data[indexes[j]], data[indexes[j + 1]])) { j++; } // data[j] 是 data[2*k]和data[2*k+1]中的最大值 if (!less(data[indexes[k]], data[indexes[j]])) { break; } swapIndexes(k, j); k = j; } } /** * 交换堆中索引为i和j的两个元素 * 有了反向索引reverse数组后，当indexes数组发生改变， * 相应的reverse数组也有发生改变 * * @param i * @param j */ private void swapIndexes(int i, int j) { int t = indexes[i]; indexes[i] = indexes[j]; indexes[j] = t; reverse[indexes[i]] = i; reverse[indexes[j]] = j; } private boolean less(T t1, T t2) { return t1.compareTo(t2) < 0; } /** * 测试 IndexMaxHeap */ public static void main(String[] args) { IndexMaxHeap indexMaxHeap = new IndexMaxHeap(10); indexMaxHeap.insert(0, 12); indexMaxHeap.insert(1, 4); indexMaxHeap.insert(2, 32); indexMaxHeap.insert(4, 13); indexMaxHeap.insert(3, 21); indexMaxHeap.change(3, 57); while (!indexMaxHeap.isEmpty()) { System.out.println("索引：" + indexMaxHeap.getMaxIndex() + " 值为：" + indexMaxHeap.extractMax()); } }}