DAY4 - 堆

昨天介绍完两个排序法，今天介绍资料结构，也会配上例题(堆在刷题的时候很常用)

Heap

• 每个node最多两个child
• 每个node都比自己的child大(小)

直接看程序

//左右子叶要是heap结构(从子叶开始heapify)
void heapify(vector<int>& arr, int root, int len){
    int l = 2*root;
    int r = 2*root+1;
    int max_node = -1;
    //若根节点已经是最大
    if(l<=len&&arr[l]>arr[root]){
        max_node = l;
    }
    else{
        max_node = root;
    }
    if(r<=len&&arr[r]>arr[max_node]){
        max_node = r;
    }
    if(root!=max_node){
        swap(arr[max_node], arr[root]);
        heapify(arr, max_node, len); //此时arr[root]是子节点
    }
}

有了heapify这个操作之後，可以把数组建成堆的形式，那就可以拿来排序~~

void build_heap(vector<int>& arr){
    //先建好heap结构
    arr.insert(arr.begin(), 0);
    for (int i = arr.size()/2; i >= 1 ; i--) { //必须要从子叶开始heapify
        heapify(arr, i, arr.size()-1);
    }
}

泛型

解决有些问题时，会使用不同型态或自定义的型态，例如天际线问题，就会写成这种functor

class event_cmp{
public:
    bool operator()(bd_event A, bd_event B){
        if(B.x < A.x){
            return true;
        }
        if(B.x==A.x){
            if(A.cover){
                return true;
            }
        }
        return false;
    }
};

priority_queue<bd_event, vector<bd_event>, event_cmp> events;

例题实战

215. 数组中的第K个最大元素
这题调用堆结构的话就很直观了~~

1878. 矩阵中最大的三个菱形和
爆搜然後放入堆~~

class Solution {
    priority_queue<int> res;
    int mmin = INT_MAX;
public:
    vector<int> getBiggestThree(vector<vector<int>>& grid) {
        int M = grid.size();
        int N = grid[0].size();
        vector<int> ans;
        for(int i = 0; i<M; ++i){
            for(int j = 0; j<N; ++j){
                find(grid, i, j);
            }
        }
        unordered_map<int, int> hash;
        while(!res.empty()&&ans.size()<3){
            if(!hash.count(res.top()) ){
                ans.push_back(res.top());
            }
            hash[res.top()]++;
            res.pop();
        }
        return ans;
        
    }
    void find(vector<vector<int>>& grid, int i, int j){
        int M = grid.size();
        int N = grid[0].size();
        int k = 1; //边长是k+1
        int ssum = 0;
        if(res.size()<=3||grid[i][j]>mmin){
            res.push(grid[i][j]);
            if(grid[i][j]<mmin){
                mmin = grid[i][j];
            }
        }
        const int dir_i[]{1, 1, -1, -1};
        const int dir_j[]{-1, 1, 1, -1};
        int ori_i = i;
        int ori_j = j;
        while(k){
            for(int m = 0; m<4; ++m){ //四个方向
                for(int n = 0; n<k; ++n){ //边长扩展
                    //cout<< i<<" "<<j<<" "<<endl;
                    ssum+=grid[i][j];
                    int next_i = i+dir_i[m];
                    int next_j = j+dir_j[m];
                    if(next_i>=M||next_i<0||next_j>=N||next_j<0){
                        return;
                    }
                    i = next_i;
                    j = next_j;
                }
            }
            if(res.size()<=3||ssum>mmin){
                res.push(ssum);
                if(ssum<mmin){
                    mmin = ssum;
                }
            }
            ssum = 0;
            i = ori_i;
            j = ori_j;
            k++;
        }
    }
    
};