Heapify

今日練習的題目是 976. Largest Perimeter Triangle，官方的解答是直接排序後，從後面開始找出第一個合法的三角形周長就可以了，不過還有另一種解法就是利用 Heapify，雖然最糟的情況下演算法效能會跟直接排序法差不多，但是最佳狀況會比排序法好，但是現實上也可能會因為排序法使用連續的記憶體也可能會效率更好一點，所以還是要看資料本身適合哪一種。

如果是使用 Python3 的話，因為預設是 Min Heap 所以會需要使用點小技巧來使用成 Max Heap 的樣子。

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums = [-num for num in nums]
        heapq.heapify(nums)
        a = -heapq.heappop(nums)
        b = -heapq.heappop(nums)
        while len(nums) > 0:
            c = -heapq.heappop(nums)
            if b + c > a:
            	return a + b + c
            a, b = b, c
        return 0

如果是使用 C++ 的話，由於預設是 Max Heap，所以直接倒進去 priority_queue 使用就可以了。

class Solution {
public:
    int largestPerimeter(vector<int>& nums) {
    	priority_queue<int> pq(nums.begin(), nums.end());
        int a = pq.top();
        pq.pop();
        int b = pq.top();
        pq.pop();
        while (!pq.empty()) {
            int c = pq.top();
            if (b + c &gt; a)
            	return a + b + c;
            pq.pop();
            swap(a, b);
            swap(b, c);
        }
        return 0;
    }
};

如果是使用 Go 的話，要自己刻一些東西搭配 container/heap 使用，使用起來相當麻煩，不然就是要使用第三方套件才會比較輕鬆些。

import "container/heap"

type IntHeap []int

func (h IntHeap) Len() int { return len(h) }

func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x any) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func largestPerimeter(nums []int) int {
	if len(nums) < 3 {
    	return 0
	}

	h := IntHeap(nums)
	heap.Init(&h)
	for h.Len() >= 3 {
    	a := heap.Pop(&h).(int)
		b := h[0] 
		c := h[1]

        if h.Len() > 2 && h[2] > c {
        	c = h[2]
        }

		if b+c > a {
        	return a + b + c
		}
	}

	return 0
}

如果是使用 Rust 的話，就需要使用到 std::collections::BinaryHeap，預設就是 Max Heap，所以使用上也算是簡單。

use std::collections::BinaryHeap;

impl Solution {
    pub fn largest_perimeter(nums: Vec<i32>) -> i32 {
        let mut heap = BinaryHeap::from(nums);

        while heap.len() >= 3 {
            let a = heap.pop().unwrap();
            let b = heap.pop().unwrap();
            let c = heap.pop().unwrap();

            if b + c > a {
                return a + b + c;
            } else {
                heap.push(b);
                heap.push(c);
            }
        }

        0
    }
}

不過 Rust 寫成排序的方法，寫起來會比較漂亮跟簡潔，充滿著滿滿的 Rust 程式碼正統風格。

impl Solution {
    pub fn largest_perimeter(mut nums: Vec<i32>) -> i32 {
        nums.sort_unstable();
        nums.windows(3)
            .rev()
            .find_map(|window| {
                if window[0] + window[1] > window[2] {
                    Some(window[0] + window[1] + window[2])
                } else {
                    None
                }
            })
            .unwrap_or(0)
    }
}