01
什麼是堆
Law
1. 堆是一種樹，由它實現的優先級隊列的插入和刪除的時間複雜度都是O(logn)，用堆實現的優先級隊列雖然和數組實現相比較刪除慢了些，但插入的時間快的多了。當速度很重要且有很多插入操作時，可以選擇堆來實現優先級隊列。
2. java的堆和數據結構堆：java的堆是程序員用new能得到的計算機內存的可用部分。而數據結構的堆是一種特殊的二叉樹。
3. 堆是具有如下特點的二叉樹：
3.1 它是完全二叉樹，也就是說除了樹的最後一層節點不需要是滿的，其他的每一層從左到右都必須是滿的。
3.2 它常常用數組實現。
3.3 堆中每一個節點都滿足堆的條件，也就是說每一個關鍵字的值都大於或等於這個節點的子節點的關鍵字值。
4. 堆在存儲器中的表示是數組，堆只是一個概念上的表示。
5. 堆的弱序：堆和二叉搜索樹相比是弱序的，在二叉搜索樹中，當前節點的值總是比左子節點的值大，卻比它的右子節點的值小，因此按序遍歷相對容易。而堆的組織規則弱，它只要求從根到葉子節點的每一條路徑，節點都是按降序排列的。同一節點的左右子節點都沒有規律。因此，堆不支持按序遍歷，也不能在堆上便利的查找指定關鍵字，因為在查找的過程中，沒有足夠的信息決定選擇通過節點的兩個那一個走向下一層。它也不能在少於O(logn)的時間內刪除一個指定的節點，因為沒有辦法找到這個節點。因此，堆的這種近乎無序的規則似乎毫無用處，不過對於快速移除最大節點的操作，以及快速插入新節點的操作，這種順序已經足夠了。這些操作是使用堆作為優先級隊列所需要的全部操作。
6. 移除操作：移除是指刪掉關鍵字值最大的節點，即根節點。移除思路如下：
6.1.移走根，
6.2.把左後一個節點移到根的位置，
6.3.一直向下篩選這個節點，知道它在一個大於它的節點之下，小於它的節點之上為止。
6.4 說明：在被篩選節點的每個暫時停留的位置，向下篩選的算法總是要檢查那一個子節點更大，然後目標節點和較大的子節點交換位置，如果要把目標節點和較小的子節點交換，那麼這個子節點就會變成大子節點的父節點，這就違背了堆的條件。
7.堆的插入：插入使用向上篩選，節點最後插入到數組最後第一個空著的單元中，數組容量大小增加1。
7.1 說明：向上篩選的算法比向下篩選的算法相對簡單，因為它不需要比較兩個子節點關鍵字值的大小，節點只有一個父節點。目標節點主要和它的父親節點換位即可。
7.2.不是真的交換：
02
優先隊列
Law
優先隊列的特點:
能保證每次取出的元素都是隊列中優先級別最高的. 優先級別可以是自定義的, 例如, 數據的數值越大, 優先級越高, 或者數據的值越小, 優先級越高, 優先級別甚至可以通過各種負責的計算得到.
應用場景:
從一堆堆雜亂無章的數據當中按照一定的順序, 逐步的篩選出部分乃至全部的數據
舉例 : 任意一個數組, 找到前k大的數
解法1:
先對數組排序, 然後依次輸出前k大的數, 自幅度將會是O(nlogn)
解法2:
使用優先隊列, 複雜度優化成O(k + nlogk)
當數據量很大的時候, 即n特別大, 而k相對較小的時候, 顯然, 利用優先隊列能有效的降低算法複雜度. 因為要找到前k大的數, 並不需要所有的數進行排序
實現:
優先隊列的本質是一個二叉堆結構, 堆在英文中叫Binary Heap, 它是利用一個數組結構來實現的完全二叉樹, 換句話說, 優先隊列的本質是一個數組, 數組裡面的每個元素既有可能是其他元素的父節點, 也有可能是其他元素的節點, 而且, 每個父節點只能有連個子節點, 很像一顆二叉樹的結構.
牢記下面優先隊列的三個重要性質
1. 數組裡面的第一個元素array[0]擁有最高的優先級別.
2. 對於一個下標i, 那麼對於元素array[i] 而言:
2.1 它的父節點所對應的元素下標是(i -1) / 2
2.2 它的左孩子所對應的元素下標是2 * i + 1
2.3它的右孩子所對應的元素下標是 2 * i+ 2
3. 數組裡每個元素的優先級別都要高於它兩個孩子的優先級別.
03
例題分析Law
347: 前K個高頻元素
給定一個非空的整數數組, 返回其中出現評率前K高的元素
給定一個非空的整數數組, 返回其中出現評率前K高的元素
示例 1:
輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]
示例 2:
輸入: nums = [1], k = 1
輸出: [1]
- 你可以假設給定的 k 總是合理的，且 1 ≤ k ≤ 數組中不相同的元素的個數。
- 你的算法的時間複雜度必須優於 O(n log n) , n 是數組的大小。
官網給出的解法
k = 1 時問題很簡單，線性時間內就可以解決。只需要用哈希表維護元素出現頻率，每一步更新最高頻元素即可。
當 k > 1 就需要一個能夠根據出現頻率快速獲取元素的數據結構，這就是優先隊列。
首先建立一個元素值對應出現頻率的哈希表。在 Java 中使用 HashMap，但需要手工填值。在 Python 中提供一個字典結構用作哈希表和在 collections 庫中的 Counter 方法去構建我們需要的哈希表。
這個步驟需要 O(N) 時間其中 N 是列表中元素個數。
第二步建立堆，堆中添加一個元素的複雜度是 O(log(k))，要進行 N 次複雜度是 O(N)。
最後一步是輸出結果，複雜度為 O(klog(k))。
在 Python 中可以使用 heapq 庫中的 nlargest 方法，可以在相同時間內完成，但只需要一行代碼解決。
代碼
class Solution {
public List<integer> topKFrequent(int[] nums, int k) {
// 使用字典，統計每個元素出現的次數，元素為鍵，元素出現的次數為值
HashMap<integer> map = new HashMap();
for(int num : nums){
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
// 遍歷map，用最小堆保存頻率最大的k個元素, 保證最上面的元素時最小的元素
PriorityQueue<integer> pq = new PriorityQueue<>(new Comparator<integer>() {
@Override
public int compare(Integer a, Integer b) {
return map.get(a) - map.get(b);
}
});
for (Integer key : map.keySet()) {
pq.add(key);
if (pq.size() > k) {
// 當元素的個數超k個, 我們就把最小, 即隊列開頭的元素刪除掉
pq.poll();
}
}
// 取出堆中的元素
List<integer> res = new ArrayList<>();
while (!pq.isEmpty()) {
res.add(pq.remove());
}
return res;
}
}/<integer>/<integer>/<integer>/<integer>/<integer>
python的解法:
class Solution:
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
count = collections.Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)
04
自己的分析
Law
如果是我自己來做的話, 這個題目的使用類型正好適合redis的sort set的數據類型, 我們直接使用redis就可以解決了, 如果你對redis的使用有任何疑問, 可以參考我原來寫過的一篇文章, redis的專題, 幫你解決任何redis的問題;
關注我
閱讀更多 故事凌 的文章
