---
# System prepended metadata

title: '**程式筆記(heap)**'
tags: [heap, code, note]

---

# **程式筆記(heap)**


:::info
:information_source: 日期 : 2023/06/07
:::


**:thumbsup:** 實作

* minHeap 最小堆積
傾向留下大數字，pop掉小數字
![](https://hackmd.io/_uploads/B1Yng_pL2.png =70%x)
* maxHeap 最大堆積
傾向留下小數字，pop掉大數字
加負號實作
![](https://hackmd.io/_uploads/SkTXWd6U2.png =70%x)


```python
import heapq (python只有最小堆積堆)

heapq.heapify(list) # 直接將list排成heap的形狀

常用的操作如下：
heapq.heappush(heap, item) # 放入
heapq.heappop(heap) # 取出
heapq.heappushpop(heap, item) # 先放入後取出

heapq.nlargest(n, heap, key=None) # 回傳iterable資料型態中 前n大元素的list
heapq.nsmallest(n, heap, key=None) # 回傳iterable資料型態中 前n小元素的list

如果heap中第一個數字沒比較出結果，那會繼續比較第二個..
```

```python
minHeap[0] -> 頂堆元素 -> 輸出最小值
minheap[1], minheap[-1] -> 沒特殊意義，不一定是第二小or最大值
largest_two = heapq.nlargest(2, minHeap) 
-> 此nlargest和nsmallest獨立於heapq，不管傳入是minHeap或maxHeap它都會回傳前n個最大或最小的數字列表
```

**:thumbsup:** 理論

* 如何建立heap
先把資料都放到heap中，從最後一個節點開始，依次判斷以這個節點為根的子數是否符合最小/大堆積的特性。一層一層往上判斷調整，直到整棵樹都符合為止

* 如何刪除
時間複雜度為Ｏ(logn)
以maxHeap為例
1. 取出最大的元素，也就是根節點，並且和樹的最後一個節點交換
2. 維持 maxHeap 父節點大於子節點的結構 : 比較根節點和左右子節點，如果子節點較大則和根節點交換。如果左右子節點都比較大，則跟較大者交換
3. 繼續重複對子節點比較的過程


* 如何插入
時間複雜度為Ｏ(logn)
1. 先將欲插入的元素放入 heap 最後一個位置
2. 比較此元素和父節點的值，有必要的時候交換
1. 繼續對父節點重複此比較的過程，直到不能再向上移動為止



---

**:thumbsup:** Kth

很常用dict配合統計次數

* Find K Closest Elements
```
取出最靠近x的k個數字 若距離相同 取小
Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]
```
```python
class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        minHeap = []
        for n in arr:
            minHeap.append([abs(n - x), n])
        
        heapify(minHeap)
        res = []

        while k:
            diff, n = heappop(minHeap)
            res.append(n)
            k -= 1
        
        return sorted(res)
```

* Kth Largest Element in an Array
```python
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        maxHeap = []
        for n in nums:
            maxHeap.append(-n)
        heapify(maxHeap)

        while k:
            res = heappop(maxHeap)
            k -= 1
        
        return -res
```

* Kth Largest Element in a Stream
minHeap傾向存大，那就固定留下k個最大的，並且用minheap[0]是最小的特性，去回傳最大裡面的最小
```
Input:
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]

Output: [null, 4, 5, 5, 8, 8]
```

```python
class KthLargest:
    def __init__(self, k: int, nums: list):
        self.nums = nums
        self.k = k
        heapq.heapify(self.nums)
        while len(self.nums) > self.k:
            heapq.heappop(self.nums)
    
    def add(self, val: int):
        heapq.heappush(self.nums, val)
        while len(self.nums) > self.k:
            heapq.heappop(self.nums)
        return self.nums[0]

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)
```

* Top K Frequent Elements
![image](https://hackmd.io/_uploads/SJeOl6236.png =50%x)

```python
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        record = collections.defaultdict(int)
        for n in nums:
            record[n] += 1
        
        maxHeap = []
        for key, val in record.items():
            maxHeap.append([-val, key])
        heapify(maxHeap)
        
        res = []
        while k and maxHeap:
            val, key = heappop(maxHeap)
            res.append(key)
            k -= 1

        return res
```


**:thumbsup:** Kth 兩list

* Find K Pairs with Smallest Sums

```
*兩list第一個元素 必定最小
*(0, 1), (1, 0)必定為第二小 (思路以此類推)
*防止重複添加(visited檢查)
```
```
Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
```
```python
class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        minHeap = [[nums1[0] + nums2[0], 0, 0]]
        res = []
        visited = set()

        while k:
            total, i, j = heappop(minHeap)
            res.append([nums1[i], nums2[j]])

            if i + 1 < len(nums1) and (i + 1, j) not in visited:
                minHeap.append([nums1[i + 1] + nums2[j], i + 1, j])
                visited.add((i + 1, j))
            if j + 1 < len(nums2) and (i, j + 1) not in visited:
                minHeap.append([nums1[i] + nums2[j + 1], i, j + 1])
                visited.add((i, j + 1))
            
            heapify(minHeap)
            k -= 1
        
        return res
```


* Merge k Sorted Lists
![image](https://hackmd.io/_uploads/BkMRnMr-Je.png =50%x)

初始化放每個list的開頭，接著永遠pop調最小的(minHeap)，再新增該list的數字
heap : 需要i在裡面，當val相同時 pop出i小的數字，heap無法比較ListNode()
```python
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        minHeap = []
        for i, l in enumerate(lists):
            if l:
                heapq.heappush(minHeap, (l.val, i, l))


        dummy = tail = ListNode()
        while minHeap:
            val, i, l = heapq.heappop(minHeap)
            tail.next = l
            if l.next:
                heapq.heappush(minHeap, (l.next.val, i, l.next))
            tail = tail.next

        return dummy.next
```




**:thumbsup:** 字母頻率

* Longest Happy String
如果後前兩個都相同則pop另一個
```
Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.
*不能連續超過3個
```
```python
class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        maxHeap = []
        res = ""
        for val, key in [(a, "a"), (b, "b"), (c, "c")]:
            if val > 0:
                heapq.heappush(maxHeap, (-val, key))
        heapq.heapify(maxHeap)

        res = ""
        while maxHeap:
            val, c = heappop(maxHeap)
            if len(res) < 2 or len(res) >= 2 and not (c == res[-1] and c == res[-2]):
                res += c
                if val + 1 != 0:
                    heappush(maxHeap, (val + 1, c))
            else:
                if maxHeap:
                    val2, c2 = heappop(maxHeap)
                    res += c2
                    if val2 + 1 != 0:
                        heappush(maxHeap, (val2 + 1, c2))
                    heappush(maxHeap, (val, c))
                else:
                    break
        return res        
```
* Reorganize String
```
Input: s = "aab"
Output: "aba"
*不能連續超過2個(兩相臨字母不能相同) 如相同 返回""
```
```python
class Solution:
    def reorganizeString(self, s: str) -> str:
        record = collections.defaultdict(int)
        for c in s:
            record[c] += 1

        maxHeap = []
        for key, val in record.items():
            heapq.heappush(maxHeap, (-val, key))
        heapq.heapify(maxHeap)

        res = ""
        while maxHeap:
            val, c = heapq.heappop(maxHeap)
            if not res or len(res) >= 1 and res[-1] != c:
                res += c
                if val + 1 != 0:
                    heapq.heappush(maxHeap, (val + 1, c))
            else:
                if maxHeap:
                    val2, c2 = heapq.heappop(maxHeap)
                    res += c2
                    if val2 + 1 != 0:
                        heapq.heappush(maxHeap, (val2 + 1, c2))
                    heapq.heappush(maxHeap, (val, c))
                else:
                    return ""
        
        return res
```





---

**:thumbsup:** 題解(雙heap)
* Find Median from Data Stream

```
想要pop出兩個中間值
   minHeap習慣存大pop小，maxHeap習慣存小pop大
-> minHeap存大來pop出最小，讓maxHeap存小來pop出最大
```

```python
class MedianFinder:

    def __init__(self):
        self.minHeap = [] # store big number, pop the smallest
        self.maxHeap = [] # store small number, pop the biggest

    def addNum(self, num: int) -> None:
        heappush(self.minHeap, num)

        if abs(len(self.maxHeap) - len(self.minHeap)) >= 2:
            n = heappop(self.minHeap)
            heapq.heappush(self.maxHeap, -n)

        # exchange
        # 必須要存在 因為如果依序加進來的是 1 2 3
        # 理想上 maxHeap = [1] -> [-1], minHeap = [2, 3]
        # 但實際上是 maxHeap = [2] - > [-2], minHeap = [1, 3]
        if self.maxHeap and self.minHeap and self.minHeap[0] < -1 * self.maxHeap[0]:
            val1 = heappop(self.minHeap)
            val2 = heappop(self.maxHeap)
            heappush(self.maxHeap, -val1)
            heappush(self.minHeap, -val2)
        
    def findMedian(self) -> float:
        if len(self.maxHeap) > len(self.minHeap): 
            return -1 * self.maxHeap[0]
        elif len(self.maxHeap) < len(self.minHeap):
            return self.minHeap[0]
        else:
            return (self.minHeap[0] + -1 * self.maxHeap[0]) / 2

# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
```

* IPO
```
Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
```
```
pop all minimum capital that is smaller than w
get one maximum profit
```

```python
class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        maxProfit = [] # pop the max first
        minCapital = [(c, p) for c, p in zip(capital, profits)] # pop the min first
        heapq.heapify(minCapital)

        while k:
            while minCapital and minCapital[0][0] <= w:
                c, p = heappop(minCapital)
                heappush(maxProfit, -1 * p)
            
            if not maxProfit: # impossible to increase w
                break
            w += -1 * heappop(maxProfit)
            k -= 1
        
        return w
```




**講解連結**
https://ithelp.ithome.com.tw/articles/10206479
https://shubo.io/binary-heap/
Provided by. ramonliao & Shubo 的程式開發筆記

###### tags: `heap` `note` `code`