堆基礎

堆(Heap)是具有這樣性質的數據結構：1/完全二叉樹 2/所有節點的值大于等于(或小于等于)子節點的值：

圖片來源：這里

堆可以用數組存儲，插入、刪除會觸發節點shift_down、shift_up操作，時間復雜度O(logn)，可視化構建堆

堆是優先級隊列(Priority queue)的底層數據結構，較常使用優先級隊列而非直接使用堆處理問題。利用堆的性質可以方便地獲取極值，例如 LeetCode 題目?215.?Kth Largest Element in an Array，時間復雜度O(nlogn)：

//215. Kth Largest Element in an Arrayint findKthLargest(vector<int>& nums, int k) {
//默認為大頂堆，等同于 priority_queue<int,vector<int>,less<int>> q;priority_queue<int> q(nums.begin(),nums.end());for(int i=0;i<k-1;i++) q.pop();return q.top();}

?

相關LeetCode題：

215.?Kth Largest Element in an Array? 題解

703.?Kth Largest Element in a Stream? 題解

295.?Find Median from Data Stream? 題解

?

將頂部節點一一取出，即可實現堆排序，例如經典的題目?23.?Merge k Sorted Lists，用優先級隊列求解時間復雜度為O(nlogk)，n為總元素數、k為list數，可視化堆排序

?

相關LeetCode題：

23.?Merge k Sorted Lists??題解

自定義優先級

對于優先級隊列，我們可以自定義優先級判斷標準，比如按元素頻次、距離、成本等。這時我們需要自定義優先級隊列的比較方式：

struct compare{bool operator()(const pair<char,int> a,const pair<char,int> b){return b.second > a.second;} };//priority_queue<Type, Container, Functional>priority_queue<pair<char,int>,vector<pair<char,int>>,compare> pq;

?

相關LeetCode題：

451.?Sort Characters By Frequency??題解

347.?Top K Frequent Elements? 題解

692.?Top K Frequent Words? 題解

973.?K Closest Points to Origin? 題解

767.?Reorganize String??題解?

?

優先級隊列與貪心

由優先級隊列可方便地取得極值，而極值本身體現了貪心(Greedy)的思想；在用到貪心思路解題時，可以考慮借助優先級隊列獲取極值。

?

相關LeetCode題：

1046.?Last Stone Weight??題解

253.?Meeting Rooms II? 題解

871.?Minimum Number of Refueling Stops? 題解

502.?IPO? 題解

358.?Rearrange String k Distance Apart? 題解

?

優先級隊列與BFS

在 算法與數據結構基礎 - 隊列(Queue) 介紹了常用隊列模擬廣度優先搜索(BFS)過程，優先級隊列作為特殊的隊列，同樣可以用于BFS、以實現對臨近節點按優先級搜索。

?

相關LeetCode題：

778.?Swim in Rising Water? 題解

407.?Trapping Rain Water II? 題解

?

轉載于:https://www.cnblogs.com/bangerlee/p/11205539.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的算法与数据结构基础 - 堆(Heap)和优先级队列(Priority Queue)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。