全面了解大頂堆和小頂堆的實現和應用

堆排序是一種非常常用的排序算法，而堆數據結構中的大頂堆和小頂堆也是非常重要的基礎概念。在本文中，我們將從以下幾個方面分別進行詳細的闡述：

一、堆的基本概念

堆可以看作是一種特殊的完全二叉樹，其每個節點都大於或小於其子節點。大頂堆是指每個節點的值都大於或等於其子節點的值，小頂堆則相反，每個節點的值都小於或等於其子節點的值。

堆可以使用數組或 linked list 來進行實現。在數組中，當我們要獲取一個節點的左子節點或右子節點時，可以利用以下公式：

    left_child_index = 2 * node_index + 1;
    right_child_index = 2 * node_index + 2;

而在 linked list 中，我們可以通過鏈表中的 next 指針來獲取左子節點和右子節點。

二、堆的基本操作

堆的基本操作包括：插入節點、刪除節點、堆化（或稱為下濾）和建堆。

插入節點：將新節點插入堆的末尾，然後將該節點上移，以保證堆的特性。

    def insert(heap, item):
        heap.append(item)
        node_index = len(heap) - 1
        while node_index > 0 and heap[(node_index-1)//2] < heap[node_index]:
            heap[(node_index-1)//2], heap[node_index] = heap[node_index], heap[(node_index-1)//2]
            node_index = (node_index-1)//2

刪除節點：將堆頂節點刪除，然後用最後一個節點來替換該節點，最後將新的節點下移，以保證堆的特性。

    def delete(heap):
        if len(heap) == 0:
            return None
        if len(heap) == 1:
            return heap.pop()
        item = heap[0]
        heap[0] = heap.pop()
        node_index = 0
        child_index = 2 * node_index + 1
        while child_index < len(heap):
            right_child_index = child_index+1 if child_index+1  heap[child_index]:
                child_index = right_child_index
            if heap[node_index] < heap[child_index]:
                heap[node_index], heap[child_index] = heap[child_index], heap[node_index]
                node_index = child_index
                child_index = 2 * node_index + 1
            else:
                break
        return item

堆化（下濾）：將一個節點下移，直到其達到正確的位置，以保證堆的特性。

    def heapify(heap, node_index, heap_size=None):
        left_child_index = 2 * node_index + 1
        right_child_index = 2 * node_index + 2
        largest = node_index
        if heap_size is not None and left_child_index  heap[largest]:
            largest = left_child_index
        if heap_size is not None and right_child_index  heap[largest]:
            largest = right_child_index
        if largest != node_index:
            heap[node_index], heap[largest] = heap[largest], heap[node_index]
            heapify(heap, largest)

建堆：建立一個堆，可以使用插入節點的方法，也可以使用堆化方法。其中，使用堆化方法建堆的時間複雜度是 O(n)，而使用插入節點的方法建堆的時間複雜度為 O(nlogn)。

    def build_heap(heap, heap_size=None):
        n = len(heap) if heap_size is None else heap_size
        for i in range(n//2-1, -1, -1):
            heapify(heap, i, heap_size=heap_size)

三、堆的應用

1. 堆排序

堆排序主要分為兩個步驟，首先使用建堆方法建立一個堆，然後，不斷地將堆頂元素取出，放入已排序部分中，然後重新調整剩餘元素組成的堆。

    def heap_sort(array):
        n = len(array)
        for i in range(n-1, 0, -1):
            array[0], array[i] = array[i], array[0]
            heapify(array, node_index=0, heap_size=i)
        return array

2. Top K 問題

Top K 問題即在一個集合中找到前 K 大的元素，在堆數據結構中，可以使用一個 K 大小的小頂堆來解決，由於小頂堆只保留 K 個元素，每次遍歷集合中的一個元素， 如果該元素大於堆頂元素，則將堆頂元素刪除，並插入該元素。

    def find_top_k(array, k):
        heap = []
        for i in array:
            if len(heap)  heap[0]:
                heap[0] = i
                heapify(heap, 0)
        return heap

3、求中位數

在一個數據流中，經常需要求其中位數，即將該數據流排好序之後，中間位置的數。使用兩個堆可以方便地解決該問題。

我們可以使用一個小頂堆和一個大頂堆，其中，大頂堆存儲數據流中較小的一半數據，小頂堆中存儲數據流中較大的一半數據。中位數因為是兩堆頂元素的平均數或者大頂堆頂，因此可以通過判斷兩堆大小來確定中位數的取值。

    class MedianFinder:
        def __init__(self):
            self.max_heap = []
            self.min_heap = []

        def add_num(self, num):
            if len(self.max_heap) == len(self.min_heap):
                if self.min_heap and num > self.min_heap[0]:
                    num = heapq.heappushpop(self.min_heap,num)
                heapq.heappush(self.max_heap,-num)
            else:
                if num < -self.max_heap[0]:
                    num = -heapq.heappushpop(self.max_heap,-num)
                heapq.heappush(self.min_heap,num)

        def find_median(self):
            if len(self.max_heap) == len(self.min_heap):
                return (-self.max_heap[0] + self.min_heap[0]) / 2.0
            else:
                return -self.max_heap[0]

堆數據結構的應用極為廣泛，同時也是算法面試中經常出現的題目，因此掌握堆的基本概念和操作方式，對我們的編程發展和提升都有着非常重要的作用。