# **程式筆記(heap)**
:::info
:information_source: 日期 : 2023/06/07
:::
**:thumbsup:** 實作
* minHeap 最小堆積
傾向留下大數字，pop掉小數字
* maxHeap 最大堆積
傾向留下小數字，pop掉大數字
加負號實作
```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
```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
初始化放每個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`
Sign in with Wallet
Connect another wallet