索引堆

╰+攻爆jí腚メ 2023-08-17 17:10 88阅读 0赞

将数组的索引重新按优先级建立新的索引；数组的索引代表从小到大的顺序，而新索引里面对应着堆的不同位置对应的数组的位置。  
如果想更改数组中的某个元素，要维护index数组（堆）；在里面找到该元素所在的位置，然后再二叉树里进行元素的改变，然后使用shiftup,shiftdown维护最大堆的性质。

<table> 
 <thead> 
  <tr> 
   <th>0</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
   <th>7</th> 
   <th>8</th> 
   <th>9</th> 
   <th>10</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>index</td> 
   <td>10</td> 
   <td>9</td> 
   <td>7</td> 
   <td>8</td> 
   <td>5</td> 
   <td>6</td> 
   <td>3</td> 
   <td>1</td> 
   <td>4</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>data</td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

假设想改变数组中4位置的data，先要通过index查到到此元素在二叉堆中存在于9的位置，然后再相应的位置改变data，之后再利用shift还原最大堆。这里在index里面用的是遍历查找的方式，此处可以进行优化。  
mian.cpp

#include <iostream>
    #include <cassert>
    #include "SortTestHelper.h"
    
    #define Priority int
    
    using namespace std;
    
    template<typename Item>
    class IndexMaxHeap{
        
    
    private:
        Item *data;
        int *indexes;
    	// 得到data里的数需要先经过index进行索引
        int count;
        int capacity;
    	// 描述索引数组的位置
        void shiftUp( int k ){
        
    
            while( k > 1 && data[indexes[k/2]] < data[indexes[k]] ){
        
                swap( indexes[k/2] , indexes[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] );
                k = j;
            }
        }
    
    public:
        IndexMaxHeap(int capacity){
         // 建立空间
    
            data = new Item[capacity+1];
            indexes = new int[capacity+1];
    
            count = 0;
            this->capacity = capacity;
        }
    	// 释放空间
        ~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[i] = item;
            indexes[count+1] = i; // 添加新的索引
            count++;
    
            shiftUp(count);
        }
    
        Item extractMax(){
        
            assert( count > 0 );
    
            Item ret = data[indexes[1]];
            swap( indexes[1] , indexes[count] );
            count--;
            shiftDown(1);
            return ret;
        }
    	// 返回的是索引index值
        int extractMaxIndex(){
        
            assert( count > 0 );
    
            int ret = indexes[1] - 1; // 外部是从0开始
            swap( indexes[1] , indexes[count] );
            count--;
            shiftDown(1);
            return ret;
        }
    
        Item getMax(){
        
            assert( count > 0 );
            return data[indexes[1]];
        }
    
        int getMaxIndex(){
        
            assert( count > 0 );
            return indexes[1]-1;
        }
    
        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]在堆中的位置
            // 之后shiftUp(j), 再shiftDown(j)
    
            for( int j = 1 ; j <= count ; j ++ ) // 遍历所有值
                if( indexes[j] == i ){
          // 找到一个j的位置，代表在堆中的位置
                    shiftUp(j);
                    shiftDown(j);
                    return;
                }
        }
    
        // test reverse index
        bool testReverseIndex(){
        
    
            int *copyIndexes = new int[count+1];
    
            for( int i = 0 ; i <= count ; i ++ ){
        
                copyIndexes[i] = indexes[i];
            }
    
            copyIndexes[0] = 0;
            std::sort(copyIndexes, copyIndexes + count + 1);
    
            bool res = true;
            for( int i = 1 ; i <= count ; i ++ )
                if( copyIndexes[i-1] + 1 != copyIndexes[i] )
                    res = res || false;
    
            delete[] copyIndexes;
    
            if( !res ){
        
                cout<<"Error 1"<<endl;
                return res;
            }
    
            return true;
        }
    };
    
    template<typename T>
    void heapSortUsingIndexMaxHeap(T arr[], int n){
        
    
        IndexMaxHeap<T> indexMaxHeap = IndexMaxHeap<T>(n);
        for( int i = 0 ; i < n ; i ++ )
            indexMaxHeap.insert( i , arr[i] );
        assert( indexMaxHeap.testReverseIndex() );
    
        for( int i = n-1 ; i >= 0 ; i -- )
            arr[i] = indexMaxHeap.extractMax();
    }
    
    int main() {
        
    
        int n = 1000000;
    
        Priority* arr = new Priority[n];
        srand(time(NULL));
        for( int i = 0 ; i < n ; i ++ )
            arr[i] = rand()%n;
        SortTestHelper::testSort("Heap Sort Using Index-Max-Heap", heapSortUsingIndexMaxHeap, arr, n);
        delete[] arr;
    
        return 0;
    }

SortTestHelper.h

//
    // Created by liuyubobobo on 8/16/16.
    //
    
    #ifndef INC_08_INDEX_HEAP_SORTTESTHELPER_H
    #define INC_08_INDEX_HEAP_SORTTESTHELPER_H
    
    #include <iostream>
    #include <algorithm>
    #include <string>
    #include <ctime>
    #include <cassert>
    #include <string>
    
    using namespace std;
    
    
    namespace SortTestHelper {
        
    
        int *generateRandomArray(int n, int range_l, int range_r) {
        
    
            int *arr = new int[n];
    
            srand(time(NULL));
            for (int i = 0; i < n; i++)
                arr[i] = rand() % (range_r - range_l + 1) + range_l;
            return arr;
        }
    
        int *generateNearlyOrderedArray(int n, int swapTimes){
        
    
            int *arr = new int[n];
            for(int i = 0 ; i < n ; i ++ )
                arr[i] = i;
    
            srand(time(NULL));
            for( int i = 0 ; i < swapTimes ; i ++ ){
        
                int posx = rand()%n;
                int posy = rand()%n;
                swap( arr[posx] , arr[posy] );
            }
    
            return arr;
        }
    
        int *copyIntArray(int a[], int n){
        
    
            int *arr = new int[n];
            copy(a, a+n, arr);
            return arr;
        }
    
        template<typename T>
        void printArray(T arr[], int n) {
        
    
            for (int i = 0; i < n; i++)
                cout << arr[i] << " ";
            cout << endl;
    
            return;
        }
    
        template<typename T>
        bool isSorted(T arr[], int n) {
        
    
            for (int i = 0; i < n - 1; i++)
                if (arr[i] > arr[i + 1])
                    return false;
    
            return true;
        }
    
        bool areSameIntArrs(int* arr, int* arr2, int n){
        
    
            std::sort(arr,arr+n);
            std::sort(arr2,arr2+n);
            for( int i = 0 ; i < n ; i ++ )
                if( arr[i] != arr2[i] )
                    return false;
            return true;
        }
    
        template<typename T>
        void testSort(const string &sortName, void (*sort)(T[], int), T arr[], int n) {
        
    
            T* arr2 = copyIntArray(arr, n);
    
            clock_t startTime = clock();
            sort(arr, n);
            clock_t endTime = clock();
            cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s"<<endl;
    
            assert(isSorted(arr, n));
            assert(areSameIntArrs(arr,arr2,n));
            delete[] arr2;
            return;
        }
    
    };
    
    #endif //INC_08_INDEX_HEAP_SORTTESTHELPER_H

反向查找表：  
新建一个数组rev，里面存放的是数组索引在index里面存在的位置。

优化：要改变数组4位置的data，通过rev可以之间知道其在index的第九个位置，然后直接到二叉堆中第九个位置改变data，而无需再遍历index寻找合适的位置。  
rev\[i\] 表示i在index中的位置  
index\[i\] = j  
rev\[j\] = i  
index \[rev\[i\]\] = i  
rev\[index\[\]\] = i  
main.cpp

#include <iostream>
    #include <cassert>
    #include "SortTestHelper.h"
    
    #define Priority int
    
    using namespace std;
    
    template<typename Item>
    class IndexMaxHeap{
        
    
    private:
        Item *data;
        int *indexes;
        int *reverse; //新的成员变量
    
        int count;
        int capacity;
    
        void shiftUp( int k ){
        
    
            while( k > 1 && data[indexes[k/2]] < data[indexes[k]] ){
        
                swap( indexes[k/2] , indexes[k] );
                reverse[indexes[k/2]] = k/2; // 把这两个位置的rev写入
                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; // 初始化为0，表示不存在
    
            count = 0;
            this->capacity = capacity;
        }
    
        ~IndexMaxHeap(){
        
            delete[] data;
            delete[] indexes;
            delete[] reverse; // 释放空间
        }
    
        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[i] = item;
            indexes[count+1] = i;
            reverse[i] = count+1; //由性质而来
            count++;
    
            shiftUp(count);
        }
    
        Item extractMax(){
        
            assert( count > 0 );
    
            Item ret = data[indexes[1]];
            swap( indexes[1] , indexes[count] );
            reverse[indexes[count]] = 0;
            reverse[indexes[1]] = 1;
            count--;
            shiftDown(1);
            return ret;
        }
    
        int extractMaxIndex(){
        
            assert( count > 0 );
    
            int ret = indexes[1] - 1;
            swap( indexes[1] , indexes[count] );
            reverse[indexes[count]] = 0;
            reverse[indexes[1]] = 1;
            count--;
            shiftDown(1);
            return ret;
        }
    
        Item getMax(){
        
            assert( count > 0 );
            return data[indexes[1]];
        }
    
        int getMaxIndex(){
        
            assert( count > 0 );
            return indexes[1]-1;
        }
    
        bool contain( int i ){
         // 布尔值
            assert( i + 1 >= 1 && i + 1 <= capacity );
            return reverse[i+1] != 0; // 从0开始的要加1
        }
    
        Item getItem( int i ){
        
            assert( contain(i) );
            return data[i+1];
        }
    
        void change( int i , Item newItem ){
        
    
            assert( contain(i) ); //确定包含索引i
            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;
    //            }
    
            int j = reverse[i];
            shiftUp( j );
            shiftDown( j );
        }
    
        // test reverse index
        bool testReverseIndex(){
        
    
            int *copyIndexes = new int[count+1];
            int *copyReverseIndexes = new int[count+1];
    
            for( int i = 0 ; i <= count ; i ++ ){
        
                copyIndexes[i] = indexes[i];
                copyReverseIndexes[i] = reverse[i];
            }
    
            copyIndexes[0] = copyReverseIndexes[0] = 0;
            std::sort(copyIndexes, copyIndexes + count + 1);
            std::sort(copyReverseIndexes, copyReverseIndexes + count + 1);
    
            bool res = true;
            for( int i = 1 ; i <= count ; i ++ )
                if( copyIndexes[i-1] + 1 != copyIndexes[i] || copyReverseIndexes[i-1] + 1 != copyReverseIndexes[i] )
                    res = res || false;
    
            delete[] copyIndexes;
            delete[] copyReverseIndexes;
    
            if( !res ){
        
                cout<<"Error 1"<<endl;
                return res;
            }
    
            for( int i = 1 ; i <= count ; i ++ )
                if( reverse[ indexes[i] ] != i ){
        
                    cout<<"Error 2"<<endl;
                    return false;
                }
    
            return true;
        }
    };
    
    template<typename T>
    void heapSortUsingIndexMaxHeap(T arr[], int n){
        
    
        IndexMaxHeap<T> indexMaxHeap = IndexMaxHeap<T>(n);
        for( int i = 0 ; i < n ; i ++ )
            indexMaxHeap.insert( i , arr[i] );
        assert( indexMaxHeap.testReverseIndex() );
    
        for( int i = n-1 ; i >= 0 ; i -- )
            arr[i] = indexMaxHeap.extractMax();
    }
    
    int main() {
        
    
        int n = 1000000;
    
        Priority* arr = new Priority[n];
        srand(time(NULL));
        for( int i = 0 ; i < n ; i ++ )
            arr[i] = rand()%n;
        SortTestHelper::testSort("Heap Sort Using Index-Max-Heap", heapSortUsingIndexMaxHeap, arr, n);
        delete[] arr;
    
        return 0;
    }

SortTestHelper.h