二叉堆瞎折腾记录 - 木东驿站 - Powered by MoodBlog

CONTENT

二叉堆瞎折腾记录

最近看到一个叫"滑动窗口的最大值"的题目,题意就是给定一个序列,然后给一个窗口值,这个窗口向右进行滑动,类似于tcp的滑动窗口,然后求每次滑动后当前窗口内元素的最大值。

这种题第一眼看到的思路是O(n*m)的方法,从第一个元素开始遍历,然后内循环在窗口范围内查找最大值,这种方法固然可靠,但随着m的提升,效率是线性下降的。后来看到一种方法是用堆来维护窗口,貌似非常合适。仔细一想其实还是有问题的,窗口每次滑动时需要删除窗口最左侧的元素,众所周知二叉堆是不支持这种随机删除操作的,而且我看了看std中优先队列提供的方法,也没有这种操作。

没办法……自己写吧……开始瞎折腾

struct Heap
{
    vector<int> data_;
};
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> res;
        if(num.empty() || size > num.size() || size < 1)
            return res;
        
        Heap heap;
        for(int i=0;i<size;i++)
        {
            heap.data_.push_back(num[i]);
        }
        heap_make(heap);
        int max = heap_get_top(heap);
        res.push_back(max);
        for(int i=0;i<num.size()-size;i++)
        {
            heap_delete_num_one(heap,num[i]);
            heap_add(heap,num[i+size]);
            max = heap_get_top(heap);
            res.push_back(max);
        }
        return res;
    }
    //建堆,不用说
    void heap_make(Heap& heap)
    {
        int size = heap.data_.size();
        for(int i=size/2;i>=0;--i)
        {
            heap_swim_down(heap,i);
        }
    }
    int heap_get_top(Heap& heap)
    {
        return heap.data_[0];
    }
    //目前只是删除遇到的第一个元素,堆结构已经改变继续删除可能会有问题,需要改进
    void heap_delete_num_one(Heap& heap,int num)
    {
        int i = 0;
        bool flag = false;
        for(i=0;i<heap.data_.size();++i)
        {
            if(heap.data_[i] == num)
            {
                flag = true;
                break;
            }
                
        }
        if(flag)
        {
            swap(heap.data_[i],heap.data_[heap.data_.size()-1]);
            heap.data_.pop_back();
            //这么写是可以保证正确性的,但是可能会有切换函数栈带来的性能下降
            heap_swim_up(heap,i);
            heap_swim_down(heap,i);
        }
    }
    void heap_add(Heap& heap,int num)
    {
        heap.data_.push_back(num);
        heap_swim_up(heap,heap.data_.size()-1);
    }
    void heap_swim_up(Heap& heap,int index)
    {
        int parent = (index-1)/2;
        while(parent >= 0)
        {
            if(heap.data_[parent] < heap.data_[index])
            {
                swap(heap.data_[parent],heap.data_[index]);
                index = parent;
                parent = (index-1)/2;
            }
            else
                return;
        }
    }
     
    void heap_swim_down(Heap& heap,int index)
    {
        int child = (index+1)*2-1;
        while(child < heap.data_.size())
        {
            if(child < heap.data_.size()-1 && heap.data_[child+1] > heap.data_[child])
                child++;
            if(heap.data_[child] > heap.data_[index])
            {
                swap(heap.data_[child],heap.data_[index]);
                index = child;
                child = (index+1)*2-1;
            }
            else
                return;
        }
         
 
    }
};


个快快 2019年06月29日 天气 晴

REMARKS

© 2018 MoodBlog 0.2 个快快 作品 | 参考主题: mathilda by fuzzz. | 鲁ICP备16047814号