Python堆的全面介紹

一、什麼是Python堆？

Python堆是一種內存數據結構，用於存儲和管理內存分配和釋放。堆是一塊內存區域，當需要在程序運行期間動態分配內存時，就可以從堆中分配內存，並將地址返回給程序。Python中的堆是由CPython解釋器維護的，是一種二叉樹結構，樹的每個節點都包含一個對象。Python堆支持動態增長和收縮，允許程序在運行時分配和釋放內存，避免了靜態內存分配的限制，提高了程序的靈活性和效率。

二、Python堆的基本操作

1. 創建堆

    
        import heapq
        heap = []
        heapq.heappush(heap, 3)
        heapq.heappush(heap, 1)
        heapq.heappush(heap, 4)
        heapq.heappush(heap, 2)
    

上述代碼創建了一個空堆，並向堆中添加了4個元素。元素會自動按升序排序。通過heappush()方法向堆中添加元素。

2. 彈出堆頂元素

    
        import heapq
        heap = [3, 1, 4, 2]
        heapq.heapify(heap)
        smallest = heapq.heappop(heap)
    

上述代碼將[3, 1, 4, 2]轉換為堆並彈出了最小元素1。heapify()方法將列錶轉換為堆，並通過heappop()方法彈出堆頂元素。

3. 獲取堆頂元素

    
        import heapq
        heap = [3, 1, 4, 2]
        heapq.heapify(heap)
        smallest = heap[0]
    

上述代碼獲取了堆中的最小元素3。直接通過heap[0]獲取堆頂元素。

三、Python堆的應用場景

1. TopK問題

在大規模數據處理中，有時需要從海量數據中找出最大或最小的K個元素。通過建立大小為K的堆，可以在O(NlogK)的時間複雜度內解決TopK問題。

    
        import heapq
        def topk(nums, k):
            heap = []
            for num in nums:
                if len(heap)  heap[0]:
                    heapq.heapreplace(heap, num)
            return heap
        
        nums = [4, 1, 7, 3, 8, 5]
        k = 3
        print(topk(nums, k))  # [5, 7, 8]
    

2. 合併有序列表

當需要將多個有序列表合併為一個有序列表時，可以通過建立堆並逐一取出堆頂元素實現排序合併。

    
        import heapq
        def merge_lists(lists):
            heap = []
            for i, lst in enumerate(lists):
                if lst:
                    heapq.heappush(heap, (lst[0], i, 0))  # 元組 (值, 表編號, 元素編號)
            merged = []
            while heap:
                val, li, ei = heapq.heappop(heap)
                merged.append(val)
                if ei + 1 < len(lists[li]):
                    heapq.heappush(heap, (lists[li][ei+1], li, ei+1))
            return merged
        
        lists = [[1, 3, 5], [2, 4, 6], [0, 7, 9]]
        print(merge_lists(lists))  # [0, 1, 2, 3, 4, 5, 6, 7, 9]
    

3. 中位數問題

求一組數據的中位數，即將一組數據分為上下兩部分的數值點。通過維護大小相等或相差1的兩個堆，分別存儲比中位數小和大的元素，可以在O(logN)的時間複雜度內實現中位數查找。

    
        import heapq
        class MedianFinder:
            def __init__(self):
                self.small = []  # 大小為N//2或N//2+1的堆，存儲比中位數小的元素
                self.large = []  # 大小為N//2的堆，存儲比中位數大的元素
                
            def addNum(self, num: int) -> None:
                if len(self.small) == len(self.large):
                    heapq.heappush(self.large, -heapq.heappushpop(self.small, -num))
                else:
                    heapq.heappush(self.small, -heapq.heappushpop(self.large, num))
                    
            def findMedian(self) -> float:
                if len(self.small) == len(self.large):
                    return (self.large[0] - self.small[0]) / 2
                else:
                    return self.large[0]
                
        mf = MedianFinder()
        mf.addNum(1)
        mf.addNum(2)
        mf.addNum(3)
        print(mf.findMedian())  # 2
    

四、Python堆的性能分析

Python堆的時間複雜度與堆中元素個數N的對數Log(N)成正比，具有高效的數據插入、刪除、查找等操作。Python堆的空間複雜度則隨元素個數N線性增長。Python堆適用於大規模數據處理、數據結構實現、算法設計等多種領域，是Python編程中非常常用和重要的內置功能。