当前位置：首页 > news >正文

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

news 来源：原创 2024/4/26 19:09:22

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

堆Heap
二叉堆Binary Heap
二叉堆
二叉堆的实现
插入(insert)
取出堆顶(extract / delete max)
优先队列(Priority Queue)
实战

堆Heap

堆(Heap)是一种高效维护集合中最大或最小元素的数据结构。

大根堆:根节点最大的堆，用于维护和查询max。
小根堆:根节点最小的堆，用于维护和查询min。

堆是一棵树，并且满足堆性质(Heap property)

大根堆任意结点的关键码>=它所有子结点的关键码(父>=子)
小根堆任意结点的关键码<=它所有子结点的关键码(父<=子)

二叉堆Binary Heap

二叉堆是堆的一种简易实现

●本质上是一棵满足堆性质的完全二叉树

常见操作

●建堆(build) : 0(N)
●查询最值(get max/min) : 0(1)
●插入(insert) : 0(log N)
●取出最值(delete max/min) : 0(log N)

斐波那契堆、配对堆等可以做到插入0(1),左偏树、斜堆等可以支持合并
这些高级数据结构就不再讲解了

二叉堆

在这里插入图片描述

二叉堆的实现

二叉堆一般使用一个一维数组来存储,利用完全二叉树的结点编号特性

假设第一个元素存储在索引(下标)为1的位置的话

索引为p的结点的左孩子的索引为p * 2
索引为p的结点的右孩子的索引为p*2+ 1
索引为p的结点的父亲的索引为p/ 2 (下取整)

假设第一个元素存储在索引(下标)为0的位置的话

索引为p的结点的左孩子的索引为p*2+ 1
索引为p的结点的右孩子的索引为p *2+ 2
索引为p的结点的父亲的索引为(p-1)/ 2 (下取整)

插入(insert)

新元素一律插入到数组heap的尾部

设插入到了索引p的位置

然后向上进行一次调整 (HeapifyUp)

●若已到达根,停止
●若满足堆性质(heap[p] <= heap[p/ 2]) ,停止
●否则交换heap[p]和heap[p/ 2], 令p=p/ 2,继续调整

时间复杂度: 0(log N)

取出堆顶(extract / delete max)

把堆顶(heap[1]) 与堆尾(heap[n])交换, 删除堆尾( 数组最后一个元素)

然后从根向下进行一次调整(Heapify Down)

●每次与左、右子结点中较大的一个比较,检查堆性质，不满足则交换
●注意判断子结点是否存在

时间复杂度: 0(log N)

在这里插入图片描述

优先队列(Priority Queue)

二叉堆是优先队列(Priority Queue) 一种简单、常见的实现，但不是最优实现

理论上二叉堆可以支持0(log N)删除任意元素，只需要

●定位该元素在堆中的结点p (可以通过在数值与索引之间建立映射得到)
●与堆尾交换,删除堆尾
●从p向上、向下各进行一次调整

不过优先队列并没有提供这个方法
在各语言内置的库中，需要支持删除任意元素时，一般使用有序集合等基于平衡二叉搜索树的实现

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;
        } 
     }
};

实战

23.合并K个升序链表
https://leetcode.cn/problems/merge-k-sorted-lists/

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;
};

239.滑动窗口最大值
https://leetcode.cn/problems/sliding-window-maximum/

对比单调队列和堆的解法
懒惰删除法

指的是需要从堆中删除一个元素(不一定是最大值)时，不直接删除，而是打上删除标记 soft delete)
等未来它作为最大值被取出时，再判断它是否已经被标记，若是则抛弃它,取下一个最大值
“懒惰"的含义一只要要删除的元素还不是最大值，在堆里多待一会儿也无妨，未来等它会影响
最大值正确性的时候再说吧

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;
};