美文网首页一步一步学习数据结构和算法
一步一步学习数据结构和算法 (四) 索引堆

一步一步学习数据结构和算法 (四) 索引堆

作者: mlya | 来源:发表于2019-06-14 10:39 被阅读0次

    索引堆

    之前建立堆的过程中所存在的问题

    将一个数组进行 heapify 之后, 数组元素的位置发生了变化, 有两个缺点:

    1. 移动元素位置可能会造成大量的性能消耗.
    2. 在有些情况下, 元素位置有其他意义, 不能随意改变元素位置.

    建立索引堆

    image

    针对每一个元素, 添加一个 index 结构, 用来完成堆的建立. 建立完成后, 原数组元素位置不变, index 的值表示在堆中对应位置的元素位置. 例如: 位置为 1 的 index 值为 10, arr[10] 位于堆的根节点, 其左孩子 index 值为 9, 表示 arr[9] 为根节点的左孩子.

    在元素比较时, 比较的是 data 数据, 在做元素交换时交换的是 index.

    索引数组的含义, 是从堆的角度, 正向的理解, 即 indexes[i] 表示, 堆中第 i 个元素对应的数据为 data[indexes[i]] (其索引为 indexes[i]).

    代码实现

    相比较于之前最大堆的实现, 改造为索引堆是很容易的, 需要做的是以下几件事:

    1. 添加索引数组, 其大小与数据大小相同.
    2. 在用户插入元素时, 需要给定该元素的索引, 该元素在数组的位置.
    3. 在比较元素大小时, 我们获取到的索引为堆中的索引 k, 需要通过 indexes[k] 的方式转换为数据的索引.
    4. 在交换元素时, 只需要交换其在 indexes 数组中的位置 swap(indexes[k], indexes[k / 2]).

    完整的索引堆实现如下:

    template<typename Item>
    class IndexMaxHeap {
    private:
        Item *data;
        int *indexes;
        int count;
        int capacity{};
    
        // 将 k 这个元素向上移动, 以满足大根堆定义
        void shiftUp(int k) {
            while (k > 1 && data[indexes[k / 2]] < data[indexes[k]]) {
                swap(indexes[k], indexes[k / 2]);
                k /= 2;
            }
        }
    
        void shiftDown(int k) {
            while (2 * k <= count) {
                int j = 2 * k;
                if (j + 1 <= count && data[indexes[j + 1]] > data[indexes[j]]) {
                    j += 1;
                }
                if (data[indexes[k]] >= data[indexes[j]]) {
                    break;
                }
                swap(indexes[k], indexes[j]);
                k = j;
            }
        }
        
        public:
        IndexMaxHeap(int capacity) {
            data = new Item[capacity + 1];
            indexes = new int[capacity + 1];
            this->capacity = capacity;
            count = 0;
        }
    
        IndexMaxHeap(Item arr[], int n) {
            data = new Item[n + 1];
            indexes = new int[capacity + 1];
            this->capacity = n;
            count = n;
            for (int i = 0; i < n; i++) {
                data[i + 1] = arr[i];
            }
            for (int i = count / 2; i >= 1; i--) {
                shiftDown(i);
            }
        }
    
        ~IndexMaxHeap() {
            delete[] data;
            delete[] indexes;
        }
    
        int size() {
            return count;
        }
    
        bool isEmpty() {
            return count == 0;
        }
    
        // 传入的 i 对于用户来说, 是从 0 开始索引的
        void insert(int i, Item item) {
            assert(count + 1 <= capacity);
            assert(i + 1 >= 1 && i + 1 <= capacity);
            i += 1;
            data[++count] = item;
            indexes[++count] = i;
            shiftUp(count);
        }
    
        Item extractMax() {
            assert(count > 0);
            Item ret = data[indexes[1]];
            indexes[1] = indexes[count--];
            shiftDown(1);
            return ret;
        }
    
        // 返回最大元素的的索引
        int extractMaxIndex() {
            assert(count > 0);
            // 对于外部用户来说, 索引减一
            int ret = indexes[1] - 1;
            indexes[1] = indexes[count--];
            shiftDown(1);
            return ret;
        }
    
        Item getItem(int i) {
            return data[i + 1];
        }
    
        void change(int i, Item newItem) {
            i += 1;
            data[i] = newItem;
    
            // 找到 indexes[j] = i, j 表示 data[i] 在堆中的位置.
            for (int j = 1; j <= count; j++) {
                if (indexes[j] == i) {
                    shiftUp(j);
                    shiftDown(j);
                    return;
                }
            }
        }
    };
    

    change 操作

    在上面的实现中, 添加了一个新的操作 create(), 用于修改指定数据位置的数据内容. 在实现中, 我们需要找到该数据对应于堆中的位置, 即找到一个 j, 使得 indexes[j] = i.

    void change(int i, Item newItem) {
        i += 1;
        data[i] = newItem;
        // 找到 indexes[j] = i, j 表示 data[i] 在堆中的位置.
        for (int j = 1; j <= count; j++) {
            if (indexes[j] == i) {
                shiftUp(j);
                shiftDown(j);
                return;
            }
        }
    }
    

    在上面的实现中, 我们通过遍历整个 indexes 数组, 找到和 i 相匹配的元素. 这一步操作的时间复杂度是 O(n), 因为后续 shiftUp()shiftDown() 操作复杂度都为 logn, 因此总体的时间复杂度可以看做 O(n). 如果同时对 n 个堆进行操作, 时间复杂度就达到了 O(n^2).

    进一步改进

    为了降低时间复杂度, 这里一个通用的方法就是建立反向索引数组, 如下图所示:

    image

    数组 rev 表示反向索引, 其含义为, 站在数据的角度来看, 这个数据所对应于堆中的位置是多少. 例如, 位于 10 处的数据, 对应于堆中的位置为 1, 即其位于根节点.

    • reverse[i] 表示索引 iindexes (堆) 中的位置

    根据其定义, 有下面两个等式成立

    • indexes[reverse[i]] = i
    • reverse[indexes[i]] = i

    在进行位置变更时, 需要同时变更:

    • indexes[i] = j
    • reverse[j] = i

    完整的实现如下:

    template<typename Item>
    class IndexMaxHeap {
    private:
        Item *data;
        int *indexes;
        int *reverse;
        int count;
        int capacity{};
    
        // 将 k 这个元素向上移动, 以满足大根堆定义
        void shiftUp(int k) {
            while (k > 1 && data[indexes[k / 2]] < data[indexes[k]]) {
                swap(indexes[k], indexes[k / 2]);
                reverse[indexes[k / 2]] = k / 2;
                reverse[indexes[k]] = k;
                k /= 2;
            }
        }
    
        void shiftDown(int k) {
            while (2 * k <= count) {
                int j = 2 * k;
                if (j + 1 <= count && data[indexes[j + 1]] > data[indexes[j]]) {
                    j += 1;
                }
                if (data[indexes[k]] >= data[indexes[j]]) {
                    break;
                }
                swap(indexes[k], indexes[j]);
                reverse[indexes[k]] = k;
                reverse[indexes[j]] = j;
                k = j;
            }
        }
    
    public:
        IndexMaxHeap(int capacity) {
            data = new Item[capacity + 1];
            indexes = new int[capacity + 1];
            reverse = new int[capacity + 1];
            for (int i = 0; i <= capacity; i++) {
                // reverse[i] = 0 表示数据 i 在堆中不存在.
                reverse[i] = 0;
            }
            this->capacity = capacity;
            count = 0;
        }
    
        IndexMaxHeap(Item arr[], int n) {
            data = new Item[n + 1];
            indexes = new int[capacity + 1];
            reverse = new int[capacity + 1];
            reverse = new int[capacity + 1];
            for (int i = 0; i <= capacity; i++) {
                // reverse[i] = 0 表示数据 i 在堆中不存在.
                reverse[i] = 0;
            }
            this->capacity = n;
            count = n;
            for (int i = 0; i < n; i++) {
                data[i + 1] = arr[i];
            }
            for (int i = count / 2; i >= 1; i--) {
                shiftDown(i);
            }
        }
    
        ~IndexMaxHeap() {
            delete[] data;
            delete[] indexes;
        }
    
        int size() {
            return count;
        }
    
        bool isEmpty() {
            return count == 0;
        }
    
        // 传入的 i 对于用户来说, 是从 0 开始索引的
        void insert(int i, Item item) {
            assert(count + 1 <= capacity);
            assert(i + 1 >= 1 && i + 1 <= capacity);
            i += 1;
            data[++count] = item;
            indexes[++count] = i;
            reverse[i] = count;
            shiftUp(count);
        }
    
        Item extractMax() {
            assert(count > 0);
            Item ret = data[indexes[1]];
            indexes[1] = indexes[count];
            reverse[indexes[1]] = 1;
            reverse[indexes[count]] = 0;
            count--;
            shiftDown(1);
            return ret;
        }
    
        // 返回最大元素的的索引
        int extractMaxIndex() {
            assert(count > 0);
            // 对于外部用户来说, 索引减一
            int ret = indexes[1] - 1;
            indexes[1] = indexes[count];
            reverse[indexes[1]] = 1;
            reverse[indexes[count]] = 0;
            shiftDown(1);
            return ret;
        }
    
        // 判断数组下标为 i 的元素, 是否存在于堆中
        bool contain(int i) {
            assert(i + 1 >= 1 && i + 1 <= capacity);
            return reverse[i + 1] != 0;
        }
    
        Item getItem(int i) {
            assert(contain(i));
            return data[i + 1];
        }
    
    
        void change(int i, Item newItem) {
            assert(contain(i));
            i += 1;
            data[i] = newItem;
    
            // 找到 indexes[j] = i, j 表示 data[i] 在堆中的位置.
            int j = reverse[i];
            shiftUp(j);
            shiftDown(j);
            return;
        }
    };
    

    相关文章

      网友评论

        本文标题:一步一步学习数据结构和算法 (四) 索引堆

        本文链接:https://www.haomeiwen.com/subject/jikufctx.html