二叉堆与自定义优先队列实现删除任意元素

template<typename T>
class custom_priority_queue : public std::priority_queue<T, std::vector<T>>
{
  public:
      bool remove(const T& value) {
        auto it = std::find(this->c.begin(), this->c.end(), value);
        if (it != this->c.end()) {
            this->c.erase(it);
            std::make_heap(this->c.begin(), this->c.end(), this->comp);
            return true;
        }
        else {
           return false;
        } 
     }
};

struct Node {
    int key;
    ListNode* listNode;
    Node(int key,ListNode* listNode) : key(key),listNode(listNode){}
    // bool operator < (const Node &rhs) const {
    //         return key > rhs.key;
    // }
};
class BinaryHeap{
public:
    BinaryHeap(){
        heap.push_back(Node(0,nullptr));
    }
    bool empty(){
        return heap.size() == 1;
    }
    Node getMin(){
        return heap[1];
    }
    void deleteMin(){
        swap(heap[1],heap[heap.size()-1]);
        heap.pop_back();
        Down(1);   
    }
    void insert(Node node){
        heap.push_back(node);
        Up(heap.size()-1);
    }
private:
    void Up(int p){
        int parent;
        while(p>1){
            parent = p/2;
            if(heap[p].key<heap[parent].key){
                swap(heap[p],heap[parent]);
                 p/=2;
            }
            else break;
        }
    }
    void Down(int p){
        int child ;
        int other ;
        while(p*2<heap.size()){
            child = p*2;
            other = p*2+1;
            if( other<heap.size() && heap[child].key>heap[other].key){
                child=other;
            }
            if(child<heap.size() && heap[child].key<heap[p].key){
                swap(heap[child],heap[p]);
                p=child;
            }
            else break;
        }
        // int child = p*2;
        // while(child < heap.size()) {
        //     int other = p*2+1;
        //     if(other < heap.size() && heap[other].key < heap[child].key)
        //         child = other;
        //     if (heap[child].key < heap[p].key) {
        //         swap(heap[child],heap[p]);
        //         p = child;
        //         child = p*2;
        //     }
        //     else break;
        // }
    }
    vector<Node> heap;
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for(ListNode* listNode : lists){
            if(listNode == nullptr) continue;
            q.insert(Node(listNode->val,listNode));
        }
        ListNode head;
        ListNode* tail = &head;
        while(!q.empty()){
            Node node = q.getMin();
            q.deleteMin();
            tail->next=node.listNode;
            tail = tail->next;
            ListNode* next = node.listNode->next;
            if(next != nullptr) {
                q.insert(Node(next->val,next));
            }
        }
        return head.next;
    }
private:
    //priority_queue<Node> q;
    BinaryHeap q;
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        for(int i=0;i<nums.size();i++){
            q.push({nums[i],i});
            if(i >= k-1){
                while(q.top().second <= i-k) q.pop();
                ans.push_back(q.top().first);
            }
        }
        return ans;
    }
private:
    priority_queue<pair<int,int>> q;
};