使用Python實現堆

介紹

堆（Heap）是一種特殊的樹形數據結構，其中每個節點都滿足其父節點的值大於或等於（小於或等於）其子節點的值。堆結構最常用於排序算法中，常見的有堆排序，堆還可以在優先隊列、圖形算法等領域中使用。

在本文中，我們將使用Python實現堆的數據結構和一些操作，例如：堆的插入、刪除、構建等。在學習過程中，您將熟悉堆的概念、碰到一些Python中的經典算法應用，並建立對計算機科學的深刻理解。

正文

一、Python實現堆的基本結構

在Python中，您可以使用列表來模擬實現堆的數據結構，其中根節點是列表的第一個元素。每個節點的左子節點在列表中的索引為2i，右子節點的索引為2i+1，父節點的索引為i/2整除（i為節點的索引，從1開始編號）。

二、堆的插入

堆的插入是指將一個節點添加到堆的末尾，再根據堆的性質把它安置在正確的位置，確保仍然是一個堆。我們首先將新元素插入堆的末尾，然後不斷跟它的父節點進行比較，如果父節點的值小於該節點的值，則交換這兩個節點的位置，直到該節點的父節點的值大於或等於該節點的值或者該節點已經上移到了根節點。

三、堆的刪除

堆的刪除操作分為兩種情況：刪除堆頂元素和刪除指定元素。

（1）刪除堆頂元素

我們首先獲取堆頂元素，即索引為1的元素，將其與最後一個元素交換位置，然後彈出最後一個元素。此時，我們需要讓堆重新滿足其性質，我們從堆的根開始比較它與其子節點的值，如果與其中的最大值交換，則繼續對交換後的節點進行相應的比較，直到該節點比其子節點都大（或小）。這樣操作之後，堆仍然滿足其性質。

（2）刪除指定元素

如果我們希望刪除堆中的任意元素，我們需要查找該元素在堆中的位置。最常見的方法是遍歷整個堆以尋找該元素，然後再執行與刪除堆頂元素相同的操作。然而，這將需要O(n)的時間，其中n是堆的大小。更快的方法是，將該元素的值替換為正無窮大（或負無窮大，具體根據堆是最大堆還是最小堆而決定），然後重複執行刪除堆頂元素的操作。

四、堆的構建

通常，在實際中需要將一個未排序的列錶轉變為一個堆，這個過程被稱為堆構建（Heapify）。

（1）堆構建的方法之一是，從最後一個非葉子節點向上進行迭代，一個接一個地執行下濾（SiftDown）操作，以確保每個節點都滿足堆的性質。在下濾過程中，我們首先將節點跟它的左右子節點比較，找到其中最大（或最小）的一個，如果該最大（或最小）的子節點比該節點大（或小），則交換兩個節點的值。

（2）堆構建的另一種方法是，從堆中的所有非葉子節點中選擇每個節點，對它們進行上濾（SiftUp）操作，以確保每個節點都滿足堆的性質。在上濾過程中，我們首先將節點跟它的父節點進行比較，如果父節點的值小於該節點的值，則交換這兩個節點的位置，直到該節點的父節點的值大於或等於該節點的值或者該節點已經上移到了根節點。

代碼部分

class Heap:
    def __init__(self, lst):
        self.data = lst
        self.size = len(lst)

    def heapify_down(self, i):
        while i * 2 <= self.size:
            max_child = self.get_max_child(i)
            if self.data[i]  0 and self.data[i] > self.get_parent(i):
            self.data[i], self.data[self.get_parent(i)] = self.data[self.get_parent(i)], self.data[i]
            i = self.get_parent(i)

    def get_max_child(self, i):
        if i * 2 + 1 > self.size or self.data[i * 2] > self.data[i * 2 + 1]:
            return i * 2
        else:
            return i * 2 + 1

    def get_parent(self, i):
        return self.data[i // 2] if i // 2 > 0 else 0

    def insert(self, val):
        self.size += 1
        self.data.append(val)
        self.heapify_up(self.size)

    def pop(self):
        max_val = self.data[1]
        self.data[1] = self.data[self.size]
        self.size -= 1
        self.data.pop()
        self.heapify_down(1)
        return max_val

小結

在本文中，我們介紹了堆的定義、基本結構和常見操作。同時，我們使用Python代碼來實現了堆的基本結構、插入和刪除操作，以及堆構建操作。

堆是一種非常重要的數據結構，有廣泛的應用。掌握堆的基本知識和算法實現，對於理解計算機科學和編程都非常有幫助。