Data Structure — Heap

5 min readSep 6, 2020

數據結構中很重要的Binary Tree二元樹，以下簡稱BT
BT用於儲存數據結構時，要想想有什麼方式可以加速搜尋
目前最常見的有兩種

1. BST 二元搜尋樹

成立條件：left leaf<parent node<right leaf
原理和二分搜尋一樣，找特定元素時間複雜度為有"幾層"layer，最佳時間複雜度為log(n) (這是在BST均衡分布的情況下)
如果都是單邊BST，worst case可以到O(n)，以下解釋

可以看到左右兩邊都是二元搜尋樹，但是有沒有平衡(balance)在搜尋效率差很多，而在插入節點時，有些樹(紅黑樹/AVL樹)可以做到自平衡，就比較複雜，這邊不講

2. Heap 二叉堆/ Max Heap/ Min Heap

由於heap要不斷調整自身結構，所以插入和刪除節點，均有"上浮"和"下沉"等動作，時間複雜度為log(n)，這邊n為heap的大小
python -> import heapq

這邊python的API比較需要記憶，h為heap結構
首要要將線性結構(如list)轉為heap結構：O(n)，且為inplace

> h = []
> heapq.heapify(h)
插入或刪除元素 log(n)
> heapq.heappop(h)
> heapq.heappush(h,val)

至於在實際應用時，什麼時候會用到heap去解呢?
關鍵就是top k frequency, k smallest, k largest

例題: https://leetcode.com/problems/top-k-frequent-elements/

一般全排序的算法，就是nlogn不能在小了
但是很多題目不需要全排序，因此可以簡化
如果只是要top k排序，時間複雜度可以簡化成n log(k)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:        dic = dict()
        for i in nums:
            dic[i] = dic.get(i,0)+1
        # {1:3,2:2,3:1}        import heapq
        # 思路1 nlogn 依照value將key全排序後取前面k個 124ms
        return [k for k,v in sorted(dic.items(), key= lambda x: x[1],reverse=True)][:k]
        
        # 思路2: 使用heapq 創造特定topk的heap，將時間複雜度縮短至nlog(k)
        
        h = []
        heapq.heapify(h)
        for key,val in dic.items():
            if len(h)<k:
                heapq.heappush(h,(val,key))
            else:
                heapq.heappush(h,(val,key))
                heapq.heappop(h) #python預設為最小堆 pop數值為最小的
        return [k for v,k in h] 
        
        #思路3
        res=[]
        max_heap = [(-val, key) for key, val in dic.items()]
        heapq.heapify(max_heap)
        for i in range(k):
            res.append(heapq.heappop(max_heap)[1])
        return res

範例 [1,1,1,2,2,3,4,4,4,4]取top 2 frequency element
第一步大家都一樣，就是用hashmap或counter去算每個出現的值
會得到 {1:3,2:2,3:1,4:5} # 1出現3次，2出現2次...
假設dictionary有的元素為n個，我們要取top k(k=2)

思路一就是dict根據value全排序: 時間複雜度O(nlogn)
{4:5, 1:3,2:2,3:1} 然後取前面k個 return ans = [4,1]

思路二就是，我們不需要全排序，其實排序k個就可以
首先創造一個min heap，維護size=k，所以insert/pop的複雜度是O(logk)
前兩個元素就直接塞進去變成(k,v要換順序)，((3,1),(2,2))
接下來(1,3)進來時，((3,1),(2,2),(1,3))就把最小的值pop掉變成((3,1),(2,2))

下一個(5,4)進來時，((3,1),(2,2),(5,4))就把最小的值pop掉變成((3,1),(5,4))

等於我會iterate all dictionary，每個步驟最多logk的複雜度，所以思路二為O(n*log(k))

思路三更特別，時間複雜度是O(Klog(n))+O(n)

這邊就要創造maxheap了，當然python沒有內建maxheap，所以塞進去的值都要是加個負數

我們iterate all dictionary，並將其轉換成heap，這邊的時間複雜度是O(n)

接下來根據k個element，去pop出想要的answer

總結heap的兩種用法
思路二：維護固定大小heap，nlogk
思路三：全部放進去heap，再pop出想要的，klogn+n

其他思路還有像是桶排序 / 快速排序，可以達到O(n)，這些都是在特定條件下的排序下可以優化的地方，這個之後再講

Data Structure — Heap

1. BST 二元搜尋樹

2. Heap 二叉堆/ Max Heap/ Min Heap

例題: https://leetcode.com/problems/top-k-frequent-elements/

Written by Jimmy Huang