实现最大索引堆

目录

  • 实现最大索引堆
    • 1、 实现
    • 2、 优化

实现最大索引堆

img

1、 实现

package com.yunche.datastructure;

/**
 * @ClassName: IndexMaxHeap
 * @Description: 最大索引堆:利用数据的索引构建成最大索引堆,使构建最大堆时只需
 * 移动索引, 而不需移动数据元素本身。
 * 注意:当最大索引堆构建完成后,最大数据元素的索引位于最大索引堆的堆顶,但其索引不一定是最大的。
 * @author: yunche
 * @date: 2018/12/25
 */
public class IndexMaxHeap<T extends Comparable> {
    /**
     * 存储索引堆中索引指向的元素
     */
    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 方法用来判断用户输入的索引是否存在。
img

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<T extends Comparable> {
    /**
     * 存储索引堆中索引指向的元素
     */
    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());
        }
    }
}