【LeetCode】Heap 堆積 – 堆著你ㄟ心

tags: leetcode

前言

這篇文章主要會先介紹在 Python 如何使用 Heap，然後不免俗的會講一題 LeetCode 的題目當作練習。

堆積 Heap

• 堆積有兩種：最大堆積 (Max Heap)、最小堆積 (Min Heap)，兩者的共通點就是根節點永遠是最重要的。
• 記住，是永遠！Forever!
• Heap 通常會用樹來表示，Heap 有兩種: Max Heap 或 Min Heap。
• Max Heap 中，Parent 永遠比 Child 還要大； Min Heap 中，Parent 永遠比 Child 還要小
• 所以如果是 Max Heap，則根節點永遠是整棵樹最大的；如果是 Min Heap，則根節點永遠是整棵樹最小的。

source: https://www.geeksforgeeks.org/heap-data-structure/

• 無論對這個 Heap 進行了怎麼樣的操作，他都應該維持根節點是最大或最小的這個特性，所以，他是永遠的。

LeetCode 技巧：Python 的 heapq 函式庫

• Python 有一個內建的 Library 叫做 heapq ，我們可以直接使用他來創造一個 Heap ，或是把一個 List 轉換成 Heap。
  
• heapq 事實上叫做 Heap Queue，因為他實做了 Priority Queue
  
• Heap 是一種資料結構 (data structure)、priority queue 是一種抽象資料型別 (abstract data type)，兩個名詞有本質上的差別，可以參考：https://stackoverflow.com/questions/18993269/difference-between-priority-queue-and-a-heap

Python heapq 實做

• heapq 函式庫預設是 Min Heap，如果你想把一個List 變成Min Heap，你可以使用 heapq.heapify() 函式
  
• 要再重複一次，heapq 預設是 Min Heap，如果你想要使用 Max Heap，你可以把數字全部乘以 -1，討論請看：https://stackoverflow.com/questions/2501457/what-do-i-use-for-a-max-heap-implementation-in-python
  
• 最常用的有三個函式：
  • heapq.heapify
  • heapq.heappop
  • heapq.heappush

import heapq
a = [8, 29, 0, 11, 28]

heapq.heapify(a)
# a: [0, 8, 11, 28, 29]
# a[0] 永遠是最小的

heapq.heappop(a)
# return 0
# a: [8, 11, 28, 29]

heapq.heappush(100, a)
# a: [8, 11, 28, 29, 100]

• heapq.heapify(a) 時間複雜度是 $O(N)$ 而不是 $O(NlogN)$ 因為他沒有實際上去做排序
  
• heapq.heapify(a) 只使用額外的 $O(1)$ 記憶體
  
• heapq.heappop(a) 取最小值，時間複雜度為 $O(1)$
  
• heapq.heappush(100, a)，把一個數丟到 heap 裡，時間複雜度為 $O(log(n))$，因為需要花些力氣讓他保持是一個 heap

題目 LeetCode 1464

思路

• 務必看清楚限制條件：
  
  
• 都是正數，所以這題只需要找最大的兩個數就可以，解法百百種，這裡提供兩個方法做比較
  
• 先把 list 做排序，並且取頭兩個數字：解法一
  
• 使用 Heap 來找最大的數字：解法二
  
• 可以想一下這兩個方法有沒有什麼優缺點？

解法一

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        nums.sort(reverse=True)
        return ( nums[0] -1 ) * ( nums[1] -1)

解法二

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            nums[i] *= -1

        heapq.heapify(nums)
        a = heapq.heappop(nums)
        b = heapq.heappop(nums)
        return (-a - 1) * (-b - 1)

筆記

HackMD 筆記: https://hackmd.io/@ga642381/ByB7OS5tj