python數據結構與算法-15

堆(heap)

前面我們講了兩種使用分治和遞歸解決排序問題的歸并排序和快速排序，中間又穿插了一把樹和二叉樹，
本章我們開始介紹另一種有用的數據結構堆(heap)，以及借助堆來實現的堆排序，相比前兩種排序算法要稍難實現一些。
最后我們簡單提一下 python 標準庫內置的 heapq 模塊。

什么是堆？

堆是一種完全二叉樹（請你回顧下上一章的概念），有最大堆和最小堆兩種。

最大堆: 對于每個非葉子節點 V，V 的值都比它的兩個孩子大，稱為最大堆特性(heap order property)
最大堆里的根總是存儲最大值，最小的值存儲在葉節點。
最小堆：和最大堆相反，每個非葉子節點 V，V 的兩個孩子的值都比它大。

堆的操作

堆提供了很有限的幾個操作：

插入新的值。插入比較麻煩的就是需要維持堆的特性。需要 sift-up 操作，具體會在視頻和代碼里解釋，文字描述起來比較麻煩。
獲取并移除根節點的值。每次我們都可以獲取最大值或者最小值。這個時候需要把底層最右邊的節點值替換到 root 節點之后
執行 sift-down 操作。

在這里插入圖片描述

堆的表示

上一章我們用一個節點類和二叉樹類表示樹，這里其實用數組就能實現堆。

在這里插入圖片描述

仔細觀察下，因為完全二叉樹的特性，樹不會有間隙。對于數組里的一個下標 i，我們可以得到它的父親和孩子的節點對應的下標：

parent = int((i-1) / 2)    # 取整
left = 2 * i + 1
right = 2 * i + 2

超出下標表示沒有對應的孩子節點。

實現一個最大堆

我們將在視頻里詳細描述和編寫各個操作

class MaxHeap(object):def __init__(self, maxsize=None):self.maxsize = maxsizeself._elements = Array(maxsize)self._count = 0def __len__(self):return self._countdef add(self, value):if self._count >= self.maxsize:raise Exception('full')self._elements[self._count] = valueself._count += 1self._siftup(self._count-1)  # 維持堆的特性def _siftup(self, ndx):if ndx > 0:parent = int((ndx-1)/2)if self._elements[ndx] > self._elements[parent]:    # 如果插入的值大于 parent，一直交換self._elements[ndx], self._elements[parent] = self._elements[parent], self._elements[ndx]self._siftup(parent)    # 遞歸def extract(self):if self._count <= 0:raise Exception('empty')value = self._elements[0]    # 保存 root 值self._count -= 1self._elements[0] = self._elements[self._count]    # 最右下的節點放到root后siftDownself._siftdown(0)    # 維持堆特性return valuedef _siftdown(self, ndx):left = 2 * ndx + 1right = 2 * ndx + 2# determine which node contains the larger valuelargest = ndxif (left < self._count and     # 有左孩子self._elements[left] >= self._elements[largest] andself._elements[left] >= self._elements[right]):  # 原書這個地方沒寫實際上找的未必是largestlargest = leftelif right < self._count and self._elements[right] >= self._elements[largest]:largest = rightif largest != ndx:self._elements[ndx], self._elements[largest] = self._elements[largest], self._elements[ndx]self._siftdown(largest)def test_maxheap():import randomn = 5h = MaxHeap(n)for i in range(n):h.add(i)for i in reversed(range(n)):assert i == h.extract()

實現堆排序

上邊我們實現了最大堆，每次我們都能 extract 一個最大的元素了，于是一個倒序排序函數就能很容易寫出來了：

def heapsort_reverse(array):length = len(array)maxheap = MaxHeap(length)for i in array:maxheap.add(i)res = []for i in range(length):res.append(maxheap.extract())return resdef test_heapsort_reverse():import randoml = list(range(10))random.shuffle(l)assert heapsort_reverse(l) == sorted(l, reverse=True)

Python 里的 heapq 模塊

python 其實自帶了 heapq 模塊，用來實現堆的相關操作，原理是類似的。請你閱讀相關文檔并使用內置的 heapq 模塊完成堆排序。
一般我們刷題或者寫業務代碼的時候，使用這個內置的 heapq 模塊就夠用了，內置的實現了是最小堆。

Top K 問題

面試題中有這樣一類問題，讓求出大量數據中的top k 個元素，比如一億個數字中最大的100個數字。
對于這種問題有很多種解法，比如直接排序、mapreduce、trie 樹、分治法等，當然如果內存夠用直接排序是最簡單的。
如果內存不夠用呢？這里我們提一下使用固定大小的堆來解決這個問題的方式。

一開始的思路可能是，既然求最大的 k 個數，是不是應該維護一個包含 k 個元素的最大堆呢？
稍微嘗試下你會發現走不通。我們先用數組的前面 k 個元素建立最大堆，然后對剩下的元素進行比對，但是最大堆只能每次獲取堆頂
最大的一個元素，如果我們取下一個大于堆頂的值和堆頂替換，你會發現堆底部的小數一直不會被換掉。如果下一個元素小于堆頂
就替換也不對，這樣可能最大的元素就被我們丟掉了。

相反我們用最小堆呢？
先迭代前 k 個元素建立一個最小堆，之后的元素如果小于堆頂最小值，跳過，否則替換堆頂元素并重新調整堆。你會發現最小堆里
慢慢就被替換成了最大的那些值，并且最后堆頂是最大的 topk 個值中的最小值。
（比如1000個數找10個，最后堆里剩余的是 [990, 991, 992, 996, 994, 993, 997, 998, 999, 995]，第一個 990 最小)

按照這個思路很容易寫出來代碼：

import heapqclass TopK:"""獲取大量元素 topk 大個元素，固定內存思路：1. 先放入元素前 k 個建立一個最小堆2. 迭代剩余元素：如果當前元素小于堆頂元素，跳過該元素（肯定不是前 k 大）否則替換堆頂元素為當前元素，并重新調整堆"""def __init__(self, iterable, k):self.minheap = []self.capacity = kself.iterable = iterabledef push(self, val):if len(self.minheap) >= self.capacity:min_val = self.minheap[0]if val < min_val:  # 當然你可以直接 if val > min_val操作，這里我只是顯示指出跳過這個元素passelse:heapq.heapreplace(self.minheap, val)  # 返回并且pop堆頂最小值，推入新的 val 值并調整堆else:heapq.heappush(self.minheap, val)  # 前面 k 個元素直接放入minheapdef get_topk(self):for val in self.iterable:self.push(val)return self.minheapdef test():import randomi = list(range(1000))  # 這里可以是一個可迭代元素，節省內存random.shuffle(i)_ = TopK(i, 10)print(_.get_topk())  # [990, 991, 992, 996, 994, 993, 997, 998, 999, 995]if __name__ == '__main__':test()

源碼

# python3
class MinHeap:def __init__(self):"""這里提供一個最小堆實現。如果面試不讓用內置的堆非讓你自己實現的話，考慮用這個簡版的最小堆實現。一般只需要實現 heqppop,heappush 兩個操作就可以應付面試題了parent: (i-1)//2。注意這么寫 int((n-1)/2)， python3 (n-1)//2當n=0結果是-1而不是0left:  2*i+1right: 2*i+2參考：https://favtutor.com/blogs/heap-in-pythonhttps://runestone.academy/ns/books/published/pythonds/Trees/BinaryHeapImplementation.htmlhttps://www.askpython.com/python/examples/min-heap"""self.pq = []def min_heapify(self, nums, k):"""遞歸調用，維持最小堆特性"""l = 2*k+1  # 左節點位置r = 2*k+2  # 右節點if l < len(nums) and nums[l] < nums[k]:smallest = lelse:smallest = kif r < len(nums) and nums[r] < nums[smallest]:smallest = rif smallest != k:nums[k], nums[smallest] = nums[smallest], nums[k]self.min_heapify(nums, smallest)def heappush(self, num):"""列表最后就加入一個元素，之后不斷循環調用維持堆特性"""self.pq.append(num)n = len(self.pq) - 1# 注意必須加上n>0。因為 python3 (n-1)//2 當n==0 的時候結果是-1而不是0!while n > 0 and self.pq[n] < self.pq[(n-1)//2]:  # parent 交換self.pq[n], self.pq[(n-1)//2] = self.pq[(n-1)//2], self.pq[n]  # swapn = (n-1)//2def heqppop(self):  # 取 pq[0]，之后和pq最后一個元素pq[-1]交換之后調用 min_heapify(0)minval = self.pq[0]last = self.pq[-1]self.pq[0] = lastself.min_heapify(self.pq, 0)self.pq.pop()return minvaldef heapify(self, nums):n = int((len(nums)//2)-1)for k in range(n, -1, -1):self.min_heapify(nums, k)def test_MinHeqp():import randoml = list(range(1, 9))random.shuffle(l)pq = MinHeap()for num in l:pq.heappush(num)res = []for _ in range(len(l)):res.append(pq.heqppop())  # 利用 heqppop,heqppush 實現堆排序def issorted(l): return all(l[i] <= l[i+1] for i in range(len(l) - 1))assert issorted(res)