C++大天井を実現

スタックというデータ構造は面接でよく聞かれますが、基本的なスタックソートだけでなく、古典的なTopK問題もスタックで実現できます.山は実は完全な二叉木です.二叉チェーンテーブルではなく配列で格納するのが便利です.だから、スタックの下層はまだ配列を維持しているが、それをカプセル化しているだけだ.次は大きな山を実現しましょう.

#include 
#include 
using namespace std;

template 
class MaxHeap{
private:
    Item *data;
    int count;
    int capacity;
    //         k        shiftUp  
    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; // j        
            //      ，       ，     ，             
            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){
        //              
        //    0        ， 1     
        //        
        data = new Item[capacity + 1];
        count = 0;
        this -> capacity = capacity;
    }
    //     
    ~MaxHeap(){
        delete[] data;
    }

    int size(){
        return  count;
    }
    bool isEmpty(){
        return count == 0;
    }

    //        ，     ，       
    void insert(Item item){
        //                  
        assert(count + 1 <= capacity);

        data[count + 1] = item;
        count++;
        shiftUp(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];
    }
};

ヒープというデータ構造は、ヒープ操作と最大値をポップアップする操作の時間的複雑さがO(logn)であり、このバランスによってバランスがよくなります.重要な2つの操作を追うのがshiftUpとshiftDown操作で、他の書籍で紹介されているheapAdjust操作と呼ばれています.