摘要:原文鏈接起步模塊實現(xiàn)了適用于列表的最小堆排序算法。本文內(nèi)容將分為三個部分,第一個部分簡單介紹模塊的使用第二部分回顧堆排序算法第三部分分析中的實現(xiàn)。總結(jié)堆排序結(jié)合圖來理解還是比較好理解的。
原文鏈接:https://www.hongweipeng.com/i...
起步heapq 模塊實現(xiàn)了適用于Python列表的最小堆排序算法。
堆是一個樹狀的數(shù)據(jù)結(jié)構(gòu),其中的子節(jié)點都與父母排序順序關(guān)系。因為堆排序中的樹是滿二叉樹,因此可以用列表來表示樹的結(jié)構(gòu),使得元素 N 的子元素位于 2N + 1 和 2N + 2 的位置(對于從零開始的索引)。
本文內(nèi)容將分為三個部分,第一個部分簡單介紹 heapq 模塊的使用;第二部分回顧堆排序算法;第三部分分析heapq中的實現(xiàn)。
heapq 的使用創(chuàng)建堆有兩個基本的方法:heappush() 和 heapify(),取出堆頂元素用 heappop()。
heappush() 是用來向已有的堆中添加元素,一般從空列表開始構(gòu)建:
import heapq data = [97, 38, 27, 50, 76, 65, 49, 13] heap = [] for n in data: heapq.heappush(heap, n) print("pop:", heapq.heappop(heap)) # pop: 13 print(heap) # [27, 50, 38, 97, 76, 65, 49]
如果數(shù)據(jù)已經(jīng)在列表中,則使用 heapify() 進行重排:
import heapq data = [97, 38, 27, 50, 76, 65, 49, 13] heapq.heapify(data) print("pop:", heapq.heappop(data)) # pop: 13 print(data) # [27, 38, 49, 50, 76, 65, 97]回顧堆排序算法
堆排序算法基本思想是:將無序序列建成一個堆,得到關(guān)鍵字最小(或最大的記錄;輸出堆頂?shù)淖钚?(大)值后,使剩余的 n-1 個元素 重又建成一個堆,則可得到n個元素的次小值 ;重復(fù)執(zhí)行,得到一個有序序列,這個就是堆排序的過程。
堆排序需要解決兩個問題:
如何由一個無序序列建立成一個堆?
如何在輸出堆頂元素之后,調(diào)整剩余元素,使之成為一個新的堆?
新添加元素和,如何調(diào)整堆?
先來看看第二個問題的解決方法。采用的方法叫“篩選”,當輸出堆頂元素之后,就將堆中最后一個元素代替之;然后將根結(jié)點值與左、右子樹的根結(jié)點值進行比較 ,并與其中小者進行交換;重復(fù)上述操作,直至葉子結(jié)點,將得到新的堆,稱這個從堆頂至葉子的調(diào)整過程為“篩選”。
如上圖所示,當堆頂 13 輸出后,將堆中末尾的 97 替代為堆頂,然后堆頂與它的子節(jié)點 38 和 27 中的小者交換;元素 97 在新的位置上在和它的子節(jié)點 65 和 49 中的小者交換;直到元素97成為葉節(jié)點,就得到了新的堆。這個過程也叫 下沉 。
讓堆中位置為 pos 元素進行下沉的如下:
def heapdown(heap, pos): endpos = len(heap) while pos < endpos: lchild = 2 * pos + 1 rchild = 2 * pos + 2 if lchild >= endpos: # 如果pos已經(jīng)是葉節(jié)點,退出循環(huán) break childpos = lchild # 假設(shè)要交換的節(jié)點是左節(jié)點 if rchild < endpos and heap[childpos] > heap[rchild]: childpos = rchild if heap[pos] < heap[childpos]: # 如果節(jié)點比子節(jié)點都小,退出循環(huán) break heap[pos], heap[childpos] = heap[childpos], heap[pos] # 交換 pos = childpos
再來看看如何解決第三個問題:新添加元素和,如何調(diào)整堆?這個的方法正好與 下沉 相反,首先將新元素放置列表的最后,然后新元素與其父節(jié)點比較,若比父節(jié)點小,與父節(jié)點交換;重復(fù)過程直到比父節(jié)點大或到根節(jié)點。這個過程使得元素從底部不斷上升,從下至上恢復(fù)堆的順序,稱為 上浮 。
將位置為 pos 進行上浮的代碼為:
def heapup(heap, startpos, pos): # 如果是新增元素,startpos 傳入 0 while pos > startpos: parentpos = (pos - 1) // 2 if heap[pos] < heap[parentpos]: heap[pos], heap[parentpos] = heap[parentpos], heap[pos] pos = parentpos else: break
第一個問題:如何由一個無序序列建立成一個堆?從無序序列的第 n/2 個元素 (即此無序序列對應(yīng)的完全二叉樹的最后一個非終端結(jié)點 )起 ,至第一個元素止,依次進行下沉:
for i in reversed(range(len(data) // 2)): heapdown(data, i)heapq 源碼分析
添加新元素到堆中的 heappush() 函數(shù):
def heappush(heap, item): """Push item onto heap, maintaining the heap invariant.""" heap.append(item) _siftdown(heap, 0, len(heap)-1)
把目標元素放置列表最后,然后進行上浮。盡管它命名叫 down ,但這個過程是上浮的過程,這個命名也讓我困惑,后來我才知道它是因為元素的索引不斷減小,所以命名 down 。下沉的過程它也就命名為 up 了。
def _siftdown(heap, startpos, pos): newitem = heap[pos] # Follow the path to the root, moving parents down until finding a place # newitem fits. while pos > startpos: parentpos = (pos - 1) >> 1 parent = heap[parentpos] if newitem < parent: heap[pos] = parent pos = parentpos continue break heap[pos] = newitem
一樣是通過 newitem 不斷與父節(jié)點比較。不一樣的是這里缺少了元素交換的過程,而是計算出新元素最后所在的位置 pos 并進行的賦值。顯然這是優(yōu)化后的代碼,減少了不斷交換元素的冗余過程。
再來看看輸出堆頂元素的函數(shù) heappop():
def heappop(heap): """Pop the smallest item off the heap, maintaining the heap invariant.""" lastelt = heap.pop() # raises appropriate IndexError if heap is empty if heap: returnitem = heap[0] heap[0] = lastelt _siftup(heap, 0) return returnitem return lastelt
通過 heap.pop() 獲得列表中的最后一個元素,然后替換為堆頂 heap[0] = lastelt ,再進行下沉:
def _siftup(heap, pos): endpos = len(heap) startpos = pos newitem = heap[pos] # Bubble up the smaller child until hitting a leaf. childpos = 2*pos + 1 # 左節(jié)點,默認替換左節(jié)點 while childpos < endpos: # Set childpos to index of smaller child. rightpos = childpos + 1 # 右節(jié)點 if rightpos < endpos and not heap[childpos] < heap[rightpos]: childpos = rightpos # 當右節(jié)點比較小時,應(yīng)交換的是右節(jié)點 # Move the smaller child up. heap[pos] = heap[childpos] pos = childpos childpos = 2*pos + 1 # The leaf at pos is empty now. Put newitem there, and bubble it up # to its final resting place (by sifting its parents down). heap[pos] = newitem _siftdown(heap, startpos, pos)
這邊的代碼將準備要下沉的元素視為新元素 newitem ,將其當前的位置 pos 視為空位置,由其子節(jié)點中的小者進行取代,反復(fù)如此,最后會在葉節(jié)點留出一個位置,這個位置放入 newitem ,再讓新元素進行上浮。
再來看看讓無序數(shù)列重排成堆的 heapify() 函數(shù):
def heapify(x): """Transform list into a heap, in-place, in O(len(x)) time.""" n = len(x) for i in reversed(range(n//2)): _siftup(x, i)
這部分就和理論上的一致,從最后一個非葉節(jié)點 (n // 2) 到根節(jié)點為止,進行下沉。
總結(jié)堆排序結(jié)合圖來理解還是比較好理解的。這種數(shù)據(jù)結(jié)構(gòu)常用于優(yōu)先隊列(標準庫Queue的優(yōu)先隊列用的就是堆)。 heapq 模塊中還有很多其他 heapreplace ,heappushpop 等大體上都很類似。
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/42933.html
摘要:是回調(diào)函數(shù),當鏈接服務(wù)器和相應(yīng)數(shù)據(jù)傳輸完畢時觸發(fā)本函數(shù)可選。僅僅是針對的,在中,已經(jīng)沒有這個模塊了,取代它的是。由于以流式讀取文件,從而速度較快,切少占用內(nèi)存,但是操作上稍復(fù)雜,需要用戶實現(xiàn)回調(diào)函數(shù)。 編寫模塊 模塊是程序 模塊就是一個擴展名為.py的Python程序。 編寫模塊 #!/usr/bin/env python # coding=utf-8 lang = python 引...
摘要:內(nèi)置的模塊接下來我們一一介紹。小伙伴們有沒有想我為何介紹這個模塊,并且和排序放在一起呢,其實在很多時候我們需要找序列中的前幾個最大值或者最小值,使用此模塊中的方法是最好不過的了。 說到排序,很多人可能第一想到的就是sorted,但是你可能不知道python中其實還有還就中方法喲,并且好多種場景下效率都會比sorted高。那么接下來我就依次來介紹我所知道的排序操作。sorted(iter...
摘要:主要介紹列表列表推導(dǎo)有關(guān)的話題,最后演示如何用列表實現(xiàn)一個優(yōu)先級隊列。笛卡爾積列表推導(dǎo)還可以生成兩個或以上的可迭代類型的笛卡爾積。兩個優(yōu)先級相同的元素和,操作按照它們被插入到隊列的順序返回。變量的作用是保證同等優(yōu)先級元素的正確排序。 這一篇是《流暢的 python》讀書筆記。主要介紹列表、列表推導(dǎo)有關(guān)的話題,最后演示如何用列表實現(xiàn)一個優(yōu)先級隊列。 Python 內(nèi)置序列類型 Pytho...
摘要:問題在某個集合中找到最大或最小的個元素解決方案使用模塊例如此外,這兩個函數(shù)都可以接受作為參數(shù),例如輸出為討論根據(jù)官方文檔對的介紹可以了解到提供了堆數(shù)據(jù)結(jié)構(gòu)的實現(xiàn),并且實現(xiàn)方式是小頂堆,也就是說每次的時候取出的是最小的元素首先使用將一個列 問題 在某個集合中找到最大或最小的N個元素 解決方案 使用heapq模塊 heapq.nlargest(n, iterable, key=None)h...
摘要:定義了一個非常類似的模塊,其函數(shù)接受兩個參數(shù),第一個參數(shù)是預(yù)先定義好的類型,第二個參數(shù),一般為一個序列。很少見到代碼輸出是中實現(xiàn)堆排序的模塊。這里主要看一下優(yōu)先級隊列定義優(yōu)先級比較輸出 array array 定義了一個非常類似list的模塊,其array 函數(shù)接受兩個參數(shù),第一個參數(shù)是預(yù)先定義好的類型,第二個參數(shù),一般為一個序列。 很少見到代碼: import array a = ...
閱讀 2571·2021-08-20 09:38
閱讀 1355·2019-08-30 15:43
閱讀 593·2019-08-29 17:13
閱讀 1601·2019-08-29 14:01
閱讀 1314·2019-08-29 13:29
閱讀 2322·2019-08-23 18:29
閱讀 2047·2019-08-23 17:51
閱讀 1915·2019-08-23 17:16