<ul id="ouw02"></ul>
  • 首頁 > 綜合 > 正文

    python實現堆(最大堆、最小堆、最小最大堆)

    2023-03-31 19:27:00來源:騰訊云  


    (資料圖)

    1. 最大堆

    class MaxHeap:    def __init__(self):        self.heap = []    def parent(self, i):        return (i - 1) // 2    def left_child(self, i):        return 2 * i + 1    def right_child(self, i):        return 2 * i + 2    def get_max(self):        if not self.heap:            return None        return self.heap[0]    def insert(self, item):        self.heap.append(item)        self._heapify_up(len(self.heap) - 1)    def extract_max(self):        if not self.heap:            return None        max_item = self.heap[0]        last_item = self.heap.pop()        if self.heap:            self.heap[0] = last_item            self._heapify_down(0)        return max_item    def _heapify_up(self, i):        while i > 0 and self.heap[i] > self.heap[self.parent(i)]:            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]            i = self.parent(i)    def _heapify_down(self, i):        max_index = i        left = self.left_child(i)        if left < len(self.heap) and self.heap[left] > self.heap[max_index]:            max_index = left        right = self.right_child(i)        if right < len(self.heap) and self.heap[right] > self.heap[max_index]:            max_index = right        if i != max_index:            self.heap[i], self.heap[max_index] = self.heap[max_index], self.heap[i]            self._heapify_down(max_index)if __name__ == "__main__":    max_heap = MaxHeap()    max_heap.insert(1)    max_heap.insert(2)    max_heap.insert(0)    max_heap.insert(8)    print(max_heap.get_max())

    2. 最小堆

    class MinHeap:    def __init__(self):        self.heap = []    def parent(self, i):        return (i - 1) // 2    def left_child(self, i):        return 2 * i + 1    def right_child(self, i):        return 2 * i + 2    def get_min(self):        if not self.heap:            return None        return self.heap[0]    def insert(self, item):        self.heap.append(item)        self._heapify_up(len(self.heap) - 1)    def extract_min(self):        if not self.heap:            return None        min_item = self.heap[0]        last_item = self.heap.pop()        if self.heap:            self.heap[0] = last_item            self._heapify_down(0)        return min_item    def _heapify_up(self, i):        while i > 0 and self.heap[i] < self.heap[self.parent(i)]:            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]            i = self.parent(i)    def _heapify_down(self, i):        min_index = i        left = self.left_child(i)        if left < len(self.heap) and self.heap[left] < self.heap[min_index]:            min_index = left        right = self.right_child(i)        if right < len(self.heap) and self.heap[right] < self.heap[min_index]:            min_index = right        if i != min_index:            self.heap[i], self.heap[min_index] = self.heap[min_index], self.heap[i]            self._heapify_down(min_index)

    3. 最小-最大堆

    最小-最大堆的性質是:樹中偶數層的每個節點都小于它的所有后代,而樹中奇數層的每個節點都大于它的所有后代。

    用途 雙端優先級隊列

    class MinMaxHeap:    def __init__(self):        self.heap = []    def parent(self, i):        return (i - 1) // 2    def left_child(self, i):        return 2 * i + 1    def right_child(self, i):        return 2 * i + 2    def get_min(self):        if not self.heap:            return None        return self.heap[0]    def get_max(self):        if not self.heap:            return None        if len(self.heap) == 1:            return self.heap[0]        if len(self.heap) == 2:            return self.heap[1] if self.heap[1] > self.heap[0] else self.heap[0]        return self.heap[1] if self.heap[1] > self.heap[2] else self.heap[2]    def insert(self, item):        self.heap.append(item)        self._heapify_up(len(self.heap) - 1)    def extract_min(self):        if not self.heap:            return None        min_item = self.heap[0]        last_item = self.heap.pop()        if self.heap:            self.heap[0] = last_item            self._heapify_down_min(0)        return min_item    def extract_max(self):        if not self.heap:            return None        max_item = self.get_max()        max_index = self.heap.index(max_item)        self.heap[max_index] = self.heap[-1]        self.heap.pop()        if max_index < len(self.heap):            self._heapify_down_max(max_index)        return max_item    def _heapify_up(self, i):        if i == 0:            return        parent = self.parent(i)        if self.heap[i] < self.heap[parent]:            self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]            self._heapify_up_max(parent)        else:            self._heapify_up_min(i)    def _heapify_up_min(self, i):        grandparent = self.parent(self.parent(i))        if i > 2 and self.heap[i] < self.heap[grandparent]:            self.heap[i], self.heap[grandparent] = self.heap[grandparent], self.heap[i]            self._heapify_up_min(grandparent)    def _heapify_up_max(self, i):        grandparent = self.parent(self.parent(i))        if i > 2 and self.heap[i] > self.heap[grandparent]:            self.heap[i], self.heap[grandparent] = self.heap[grandparent], self.heap[i]            self._heapify_up_max(grandparent)    def _heapify_down_min(self, i):        while True:            min_index = i            left = self.left_child(i)            if left < len(self.heap) and self.heap[left] < self.heap[min_index]:                min_index = left            right = self.right_child(i)            if right < len(self.heap) and self.heap[right] < self.heap[min_index]:                min_index = right            if i != min_index:                self.heap[i], self.heap[min_index] = self.heap[min_index], self.heap[i]                i = min_index            else:                break    def _heapify_down_max(self, i):        while True:            max_index = i            left = self.left_child(i)            if left < len(self.heap) and self.heap[left] > self.heap[max_index]:                max_index = left            right = self.right_child(i)            if right < len(self.heap) and self.heap[right] > self.heap[max_index]:                max_index = right            if i != max_index:                self.heap[i], self.heap[max_index] = self.heap[max_index], self.heap[i]                i = max_index            else:                break

    在這個實現中,MinMaxHeap類代表一個min-max堆,包含一個list堆,用于存放堆中的元素。 parent、left_child 和right_child 方法分別返回節點的父節點、左子節點和右子節點的索引。 get_min 方法返回堆中的最小元素,get_max 方法返回堆中的最大元素。 insert 方法將一個元素插入到堆中并維護堆屬性。 extract_min 方法從堆中移除最小元素并保持堆屬性。 extract_max 方法從堆中移除最大元素并保持堆屬性。

    _heapify_up、_heapify_up_min、_heapify_up_max、_heapify_down_min 和 _heapify_down_max 方法用于維護最小-最大堆屬性。 _heapify_up 在向堆中插入元素后調用,以確保元素位于正確的位置。 _heapify_up_min 和 _heapify_up_max 由 _heapify_up 調用以維護最小-最大堆屬性。 _heapify_down_min 和 _heapify_down_max 分別被 extract_min 和 extract_max 調用,以維護 min-max 堆屬性。

    標簽:

    相關閱讀

    精彩推薦

    相關詞

    推薦閱讀

    亚洲中文久久精品无码1| 亚洲?v无码国产在丝袜线观看| 亚洲精品亚洲人成在线播放| 亚洲av无码av制服另类专区| 亚洲精品视频免费| 亚洲av无码片vr一区二区三区| 亚洲AV无码乱码麻豆精品国产| 亚洲日韩国产精品无码av| 亚洲精品私拍国产福利在线| 亚洲AV无码精品色午夜在线观看| 久久精品国产亚洲网站| 伊伊人成亚洲综合人网7777| 亚洲精品综合久久| 亚洲国产成人五月综合网| 亚洲?v无码国产在丝袜线观看 | 亚洲高清国产拍精品26U| 中文字幕在线亚洲精品| 久久久久无码专区亚洲av| 亚洲人成人无码网www国产| 亚洲区不卡顿区在线观看| 在线亚洲精品自拍| 国产亚洲精品精华液| 久久精品国产99精品国产亚洲性色| 欧洲亚洲国产清在高| 亚洲AV永久无码精品成人| 久久精品国产亚洲| 亚洲色四在线视频观看| 亚洲精品美女视频| 亚洲欧洲国产综合| 亚洲婷婷天堂在线综合| 亚洲人成77777在线播放网站不卡| 久久精品国产亚洲av麻豆蜜芽 | 亚洲色WWW成人永久网址| 亚洲精品无码成人AAA片| 国产成A人亚洲精V品无码性色| 亚洲欧洲日产国码久在线观看 | 精品亚洲一区二区三区在线播放| 亚洲色婷婷六月亚洲婷婷6月| 亚洲成AV人片天堂网无码| 亚洲视频一区调教| 亚洲三级视频在线|