和堆相关的问题

小咪咪 2023-08-17 17:12 107阅读 0赞

# 使用堆实现优先队列 #

动态选择优先级最高的任务实行；既可以修改优先级别也可以加入新的任务。  
也可以在N个元素中选出前M个元素，使用优先队列N l o g M log\_M logM

# 多路归并排序 #

归并时每次比较多部分的元素，将这些元素放入堆中，然后直接选出优先级最高的元素，选出后继续补充新的元素；极端情况是一个元素是一部分，归并排序退化成了堆排序；取几部分是一个超参数。

# 二叉堆到d-叉堆 #

每个父节点要有d个子节点。d是一个超参数，一般2可以解决大部分问题。

# 堆的实现细节优化 #

shiftup和shiftdown中使用赋值操作代替swap操作；  
表示堆的操作从0开始；  
没有capacity的限制，动态的调整堆中数组的大小（原来是固定的大小）

# 最大最小队列 #

最大堆和最小堆同时维护同一组数据，同时获得最大和最小值。

mian.cpp

#include <iostream>
    #include "MaxHeap.h"
    #include "MinHeap.h"
    #include "IndexMaxHeap.h"
    #include "IndexMinHeap.h"
    #include "SortTestHelper.h"
    
    using namespace std;
    
    template<typename T>
    void heapSortUsingMaxHeap(T arr[], int n){
        
    
        MaxHeap<T> maxheap = MaxHeap<T>(n);
        for( int i = 0 ; i < n ; i ++ )
            maxheap.insert(arr[i]);
    
        for( int i = n-1 ; i >= 0 ; i-- )
            arr[i] = maxheap.extractMax();
    
    }
    
    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]);
    
        for( int i = n-1 ; i >= 0 ; i-- )
            arr[i] = indexMaxheap.extractMax();
    
    }
    
    template<typename T>
    void heapSortUsingMinHeap(T arr[], int n){
        
    
        MinHeap<T> minheap = MinHeap<T>(n);
        for( int i = 0 ; i < n ; i ++ )
            minheap.insert(arr[i]);
    
        for( int i = 0 ; i < n ; i++ )
            arr[i] = minheap.extractMin();
    
    }
    
    template<typename T>
    void heapSortUsingIndexMinHeap(T arr[], int n){
        
    
        IndexMinHeap<T> indexMinheap = IndexMinHeap<T>(n);
        for( int i = 0 ; i < n ; i ++ )
            indexMinheap.insert(i, arr[i]);
    
        for( int i = 0 ; i < n ; i++ )
            arr[i] = indexMinheap.extractMin();
    
    }
    
    int main() {
        
    
        int n = 1000000;
    
        int* arr1 = SortTestHelper::generateRandomArray(n,0,n);
        int* arr2 = SortTestHelper::copyIntArray(arr1, n);
        int* arr3 = SortTestHelper::copyIntArray(arr1, n);
        int* arr4 = SortTestHelper::copyIntArray(arr1, n);
    
        SortTestHelper::testSort("Heap Sort Using Max Heap", heapSortUsingMaxHeap, arr1, n);
        SortTestHelper::testSort("Heap Sort Using Index Max Heap", heapSortUsingIndexMaxHeap, arr2, n);
        SortTestHelper::testSort("Heap Sort Using Min Heap", heapSortUsingMinHeap, arr3, n);
        SortTestHelper::testSort("Heap Sort Using Index Min Heap", heapSortUsingIndexMinHeap, arr4, n);
    
        delete[] arr1;
        delete[] arr2;
        delete[] arr3;
        delete[] arr4;
    
        return 0;
    }

MinHeap,h

//
    // Created by liuyubobobo on 9/13/16.
    //
    
    #ifndef HEAP_MINHEAP_H
    #define HEAP_MINHEAP_H
    
    #include <algorithm>
    #include <cassert>
    
    using namespace std;
    
    
    template<typename Item>
    class MinHeap{
        
    
    private:
        Item *data;
        int count;
        int capacity;
    
        void shiftUp(int k){
        
            while( k > 1 && data[k/2] > data[k] ){
        
                swap( data[k/2], data[k] );
                k /= 2;
            }
        }
    
        void shiftDown(int k){
        
            while( 2*k <= count ){
        
                int j = 2*k;
                if( j+1 <= count && data[j+1] < data[j] ) j ++;
                if( data[k] <= data[j] ) break;
                swap( data[k] , data[j] );
                k = j;
            }
        }
    
    public:
    
        MinHeap(int capacity){
        
            data = new Item[capacity+1];
            count = 0;
            this->capacity = capacity;
        }
    
        MinHeap(Item arr[], int n){
        
            data = new Item[n+1];
            capacity = n;
    
            for( int i = 0 ; i < n ; i ++ )
                data[i+1] = arr[i];
            count = n;
    
            for( int i = count/2 ; i >= 1 ; i -- )
                shiftDown(i);
        }
    
        ~MinHeap(){
        
            delete[] data;
        }
    
        int size(){
        
            return count;
        }
    
        bool isEmpty(){
        
            return count == 0;
        }
    
        void insert(Item item){
        
            assert( count + 1 <= capacity );
            data[count+1] = item;
            shiftUp(count+1);
            count ++;
        }
    
        Item extractMin(){
        
            assert( count > 0 );
            Item ret = data[1];
            swap( data[1] , data[count] );
            count --;
            shiftDown(1);
            return ret;
        }
    
        Item getMin(){
        
            assert( count > 0 );
            return data[1];
        }
    };
    
    #endif //HEAP_MINHEAP_H

MaxHeap.h

//
    // Created by liuyubobobo on 9/13/16.
    //
    
    #ifndef HEAP_MAXHEAP_H
    #define HEAP_MAXHEAP_H
    
    #include <algorithm>
    #include <cassert>
    
    using namespace std;
    
    
    template<typename Item>
    class MaxHeap{
        
    
    private:
        Item *data;
        int count;
        int capacity;
    
        void shiftUp(int k){
        
            while( k > 1 && data[k/2] < data[k] ){
        
                swap( data[k/2], data[k] );
                k /= 2;
            }
        }
    
        void shiftDown(int k){
        
            while( 2*k <= count ){
        
                int j = 2*k;
                if( j+1 <= count && data[j+1] > data[j] ) j ++;
                if( data[k] >= data[j] ) break;
                swap( data[k] , data[j] );
                k = j;
            }
        }
    
    public:
    
        MaxHeap(int capacity){
        
            data = new Item[capacity+1];
            count = 0;
            this->capacity = capacity;
        }
    
        MaxHeap(Item arr[], int n){
        
            data = new Item[n+1];
            capacity = n;
    
            for( int i = 0 ; i < n ; i ++ )
                data[i+1] = arr[i];
            count = n;
    
            for( int i = count/2 ; i >= 1 ; i -- )
                shiftDown(i);
        }
    
        ~MaxHeap(){
        
            delete[] data;
        }
    
        int size(){
        
            return count;
        }
    
        bool isEmpty(){
        
            return count == 0;
        }
    
        void insert(Item item){
        
            assert( count + 1 <= capacity );
            data[count+1] = item;
            shiftUp(count+1);
            count ++;
        }
    
        Item extractMax(){
        
            assert( count > 0 );
            Item ret = data[1];
            swap( data[1] , data[count] );
            count --;
            shiftDown(1);
            return ret;
        }
    
        Item getMax(){
        
            assert( count > 0 );
            return data[1];
        }
    };
    
    #endif //HEAP_MAXHEAP_H

IndexMinHeap.h

//
    // Created by liuyubobobo on 9/13/16.
    //
    
    #ifndef HEAP_INDEXMINHEAP_H
    #define HEAP_INDEXMINHEAP_H
    
    #include <iostream>
    #include <algorithm>
    #include <cassert>
    
    using namespace std;
    
    
    template<typename Item>
    class IndexMinHeap{
        
    
    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;
                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]] > data[indexes[j+1]] )
                    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:
        IndexMinHeap(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;
    
            count = 0;
            this->capacity = capacity;
        }
    
        ~IndexMinHeap(){
        
            delete[] data;
            delete[] indexes;
            delete[] reverse;
        }
    
        int size(){
        
            return count;
        }
    
        bool isEmpty(){
        
            return count == 0;
        }
    
        void insert(int index, Item item){
        
            assert( count + 1 <= capacity );
            assert( index + 1 >= 1 && index + 1 <= capacity );
    
            index += 1;
            data[index] = item;
            indexes[count+1] = index;
            reverse[index] = count+1;
            count++;
            shiftUp(count);
        }
    
        Item extractMin(){
        
            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 extractMinIndex(){
        
            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 getMin(){
        
            assert( count > 0 );
            return data[indexes[1]];
        }
    
        int getMinIndex(){
        
            assert( count > 0 );
            return indexes[1]-1;
        }
    
        bool contain( int index ){
        
    
            return reverse[index+1] != 0;
        }
    
        Item getItem( int index ){
        
            assert( contain(index) );
            return data[index+1];
        }
    
        void change( int index , Item newItem ){
        
    
            assert( contain(index) );
            index += 1;
            data[index] = newItem;
    
            shiftUp( reverse[index] );
            shiftDown( reverse[index] );
        }
    
    };
    
    #endif //HEAP_INDEXMINHEAP_H

IndexMaxHeap.h

//
    // Created by liuyubobobo on 9/13/16.
    //
    
    #ifndef HEAP_INDEXMAXHEAP_H
    #define HEAP_INDEXMAXHEAP_H
    
    #include <iostream>
    #include <algorithm>
    #include <cassert>
    
    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;
                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;
    
            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;
        }
    
        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;
    
            int j = reverse[i];
            shiftUp( j );
            shiftDown( j );
        }
    
    };
    
    #endif //HEAP_INDEXMAXHEAP_H

SortTestHelper.h

//
    // Created by liuyubobobo on 9/13/16.
    //
    
    #ifndef HEAP_SORTTESTHELPER_H
    #define 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;
        }
    
        template<typename T>
        void testSort(const string &sortName, void (*sort)(T[], int), T arr[], int 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));
    
            return;
        }
    
    };
    
    #endif //HEAP_SORTTESTHELPER_H