堆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; };
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
