今日題目

題目連結：1046. Last Stone Weight
題目主題：Array, Heap(Priority Queue)

今天的重點一樣在Heap (Priority Queue)這個主題上面，這次會分享Heap (Priority Queue)實際上長的樣子及pop資料的過程。

簡單說說 Heap(Priority Queue)

上一篇分享了Heap的使用概念，另外也有提到Heap其實是一個Tree的結構，這次就拿一個範例，來看看將陣列放進箱子後，實際上會長成什麼樣子。範例一樣使用Min Heap來說明，以Python為例，當我們呼叫了heapify()實際上，到底對陣列做了什麼改變？而heappop()又是怎麼運作的呢？

範例資料：nums = [13, 14, 11, 1, 4, 6, 16]

當我們將這個nums的資料轉成Min Heap後，也就是使用heapify(nums)後，實際上這個資料轉換後的結構長相如下圖。

這種樹的原則是越上層的數字越小，越下層的數字越大，數字不見得會依照順序排，但上層小、下層大的原則是一定的。假設是Max Heap，原則是越上層的數字越大，越下層的數字越小。

還記得前一篇講到當我們對這個Min Heap取一筆資料時，一定會優先取得最小的數字，這個資料的取得過程，實際上運作如下圖：

1. 最上面的最小數字會跟最下層的最後一個數字交換，這個最小數字就會被pop移出這棵樹了。
2. 而移到上面的目的是要讓原則保持下去，因此這個被換上來的數字會開始往下層子節點去找，它會跟下層子節點中最小的數字交換。
3. 若有交換，會繼續做第 2 步驟一樣的事，直到下層子節點的數字比較大或沒有子節點才會停下來。

再讓我們看一個例子，如果在取一筆資料，運作過程會如下圖：

可以看到這個數字 11 被換到最上面以後，這次是往下層右子節點走，是因為 6 是它下層子節點中最小的，換完以後就停止了，因為沒有下層沒有子節點了。

可以在上面兩個pop例子中看到，這棵樹在取完資料的過程，會一直保持樹的原則，越上層的數字越小，越下層的數字越大。

這是本系列文第一次看到樹的結構，接下來會越來越多樹的例子，在這邊我們只要先知道Heap(Priority Queue)實際的長相及pop運作過程即可。

題目解說

建議可以看看LeetCode原本的題目說明，這邊是用我的方式說明題目，參考就好。

本題會輸入一個stones陣列，這個陣列存放的每個值代表一顆石頭的重量。
這是一個遊戲，每回合會選兩顆最重的石頭互敲敲碎，假設最重的兩顆石頭分別為 x 及 y，敲碎的規則如下：

• x == y，這兩顆石頭都會完全被銷毀。
• x != y，x 會被銷毀，而 y 會變成一顆重量為 y - x 的石頭。

依照上面的規則，會一直玩到剩下一顆石頭或是沒有石頭才會結束遊戲。最終如果剩一顆石頭，回傳最後這顆石頭的重量，若最終沒有任何石頭，直接回傳０。

約束：

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 1000

範例1

輸入: stones = [2,7,4,1,8,1]
輸出: 1
解釋: 
第一回合 最重兩顆石頭為 7 跟 8 ，敲完以後會拿到 1 這顆石頭，放回stones中，剩[2,4,1,1,1]。
第二回合 最重兩顆石頭為 2 跟 4 ，敲完以後會拿到 2 這顆石頭，放回stones中，剩[2,1,1,1]。
第三回合 最重兩顆石頭為 2 跟 1 ，敲完以後會拿到 1 這顆石頭，放回stones中，剩[1,1,1]。
第四回合 最重兩顆石頭為 1 跟 1 ，敲完以後兩顆都被銷毀，stones中剩[1]。
最後回傳這顆石頭重量 1。

範例2

輸入: stones = [1]
輸出: 1
解釋: 因為只有一顆石頭，直接回傳這顆石頭的重量。

建議到這邊先停下來，嘗試自己解解看，若沒有想法可再繼續走下去。

解題的想像

文字描述

1. 使用Max Heap來處理。
2. 跑一個迴圈，每圈都從Max Heap取兩個值出來:
   • 第一個值放進 y、第二個值放進 x
   • y - x 取得y石頭的新重量。
   • 若新的重量大於 0 要再放回Max Heap，繼續下一次的遊戲。
   • 若石頭剩一顆或沒有石頭時結束迴圈。
3. 如果石頭剩一顆，回傳這顆石頭的重量，若沒有石頭回傳 0。

圖解過程

範例: stones = [2,7,4,1,8,1]

上圖範例可以看到，每個步驟會取得兩顆石頭，step2 開始會看到的綠色數字，就是前一步驟中y - x 得到的新石頭重量。直接看step4 取到的 y 跟 x 都是1，因此直接抵銷，最終step 5 剩一個石頭，所以回傳這顆石頭結束。

若因為沒想法而走到這邊，建議看完想像以後再給自己一次機會試一次。

程式碼撰寫

from heapq import _heapify_max, _heappop_max, heappush

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # 跑一個迴圈，到剩一顆石頭或沒石頭時結束
        while len(stones) > 1:
            # 整理成Max Heap的結構
            _heapify_max(stones)
            # 最重的石頭放 y
            y = _heappop_max(stones)
            # 第二重的石頭放 x
            x = _heappop_max(stones)
            # 取得新重量
            newWeight = y-x
            # 若不是 0，要再把這顆有新重量的石頭放回stones中
            if newWeight > 0:
                heappush(stones, newWeight)
        # 若剩一顆，回傳這顆石頭重量
        # 若沒有剩任何石頭回傳 0
        return stones[0] if len(stones) == 1 else 0

希望您今天能瞭解到...

1. Heap(Priority Queue) 的真面目
2. 1046. Last Stone Weight 解題方法

若內容有什麼問題或建議歡迎一起交流：）
感謝您今天願意花時間看完這篇文章~~~~

Next：144. Binary Tree Preorder Traversal