Python排序搜索基本算法之堆排序?qū)嵗斀?/h1>
更新時(shí)間：2017年12月08日 11:33:14 作者：littlethunder
這篇文章主要介紹了Python排序搜索基本算法之堆排序,結(jié)合實(shí)例形式詳細(xì)分析了堆排序的原理、Python實(shí)現(xiàn)方法及相關(guān)操作注意事項(xiàng),需要的朋友可以參考下
本文實(shí)例講述了Python排序搜索基本算法之堆排序。分享給大家供大家參考，具體如下：
堆是一種完全二叉樹，堆排序是一種樹形選擇排序，利用了大頂堆堆頂元素最大的特點(diǎn)，不斷取出最大元素，并調(diào)整使剩下的元素還是大頂堆，依次取出最大元素就是排好序的列表。舉例如下，把序列[26,5,77,1,61,11,59,15,48,19]排序，如下：
基于堆的優(yōu)先隊(duì)列算法代碼如下：
def fixUp(a): #在堆尾加入新元素，fixUp恢復(fù)堆的條件
k=len(a)-1
while k>1 and a[k//2]<a[k]:
a[k//2],a[k]=a[k],a[k//2]
k=k//2
def fixDown(a): #取a[1]返回的值，然后把a(bǔ)[N]移到a[1]，fixDown來恢復(fù)堆的條件
k=1
N=len(a)-1
while 2*k<=N:
j=2*k
if j<N and a[j]<a[j+1]:
j+=1
if a[k]<a[j]:
a[k],a[j]=a[j],a[k]
k=j
else:
break
def insert(a,elem):
a.append(elem)
fixUp(a)
def delMax(a):
maxElem=a[1]
N=len(a)
if N<=1:
print('There\'s none element in the list')
return -1
if N==2:
return a[1]
else:
a[1]=a.pop()
fixDown(a)
return maxElem
data=[-1,] #第一個(gè)元素不用，占位
insert(data,26)
insert(data,5)
insert(data,77)
insert(data,1)
insert(data,61)
insert(data,11)
insert(data,59)
insert(data,15)
insert(data,48)
insert(data,19)
result=[]
N=len(data)-1
for i in range(N):
print(data)
result.append(delMax(data))
print(result)
fixUp函數(shù)用于向列表的尾部添加一個(gè)新的元素，然后調(diào)整成大頂堆；fixDown函數(shù)用于取出大頂堆最大的元素后，把列表尾部的元素放到堆頂位置，然后再調(diào)整成大頂堆；insert函數(shù)是每次插入一個(gè)新的元素并調(diào)整成為大頂堆；delMax函數(shù)把最大的元素返回出來并把剩下的元素調(diào)整成為大頂堆。
輸出如下：
[-1, 77, 61, 59, 48, 19, 11, 26, 1, 15, 5]
[-1, 61, 48, 59, 15, 19, 11, 26, 1, 5]
[-1, 59, 48, 26, 15, 19, 11, 5, 1]
[-1, 48, 19, 26, 15, 1, 11, 5]
[-1, 26, 19, 11, 15, 1, 5]
[-1, 19, 15, 11, 5, 1]
[-1, 15, 5, 11, 1]
[-1, 11, 5, 1]
[-1, 5, 1]
[-1, 1]
[77, 61, 59, 48, 26, 19, 15, 11, 5, 1]
前面的輸出是不斷取出最大元素后的大頂堆，由于是完全二叉樹，根據(jù)列表可以自己寫出大頂堆的樹形結(jié)構(gòu)，就不在這里贅述，最后一行是排好序的列表。
下面是堆排序算法，代碼如下：
def fixDown(a,k,n): #自頂向下堆化，從k開始堆化
N=n-1
while 2*k<=N:
j=2*k
if j<N and a[j]<a[j+1]: #選出左右孩子節(jié)點(diǎn)中更大的那個(gè)
j+=1
if a[k]<a[j]:
a[k],a[j]=a[j],a[k]
k=j
else:
break
def heapSort(l):
n=len(l)-1
for i in range(n//2,0,-1):
fixDown(l,i,len(l))
while n>1:
l[1],l[n]=l[n],l[1]
fixDown(l,1,n)
n-=1
return l[1:]
l=[-1,26,5,77,1,61,11,59,15,48,19] #第一個(gè)元素不用，占位
res=heapSort(l)
print(res)
輸出如下：
[1, 5, 11, 15, 19, 26, 48, 59, 61, 77]
PS：這里再為大家推薦一款關(guān)于排序的演示工具供大家參考：
在線動(dòng)畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
http://tools.jb51.net/aideddesign/paixu_ys
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》
希望本文所述對大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
-
基于python圖書館管理系統(tǒng)設(shè)計(jì)實(shí)例詳解
這篇文章主要介紹了基于python圖書館管理系統(tǒng)設(shè)計(jì)實(shí)例詳解，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧 2020-08-08
-
這篇文章主要介紹了Python 去除字符串中指定字符串,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧 2020-03-03
-
這篇文章主要為大家介紹了python庫matplotlib繪制坐標(biāo)圖，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下 2019-10-10
-
python實(shí)戰(zhàn)scrapy操作cookie爬取博客涉及browsercookie
這篇文章主要為大家介紹了python實(shí)戰(zhàn)scrapy操作cookie爬取博客涉及browsercookie，下面來學(xué)習(xí)一下 scrapy 操作 Cookie來爬取博客吧 2021-11-11
-
今天小編就為大家分享一篇基于Python List的賦值方法，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧 2018-06-06
-
python實(shí)現(xiàn)的批量分析xml標(biāo)簽中各個(gè)類別個(gè)數(shù)功能示例
這篇文章主要介紹了python實(shí)現(xiàn)的批量分析xml標(biāo)簽中各個(gè)類別個(gè)數(shù)功能,涉及Python針對xml文件的遍歷、讀取、解析等相關(guān)操作技巧,需要的朋友可以參考下 2019-12-12
-
這篇文章主要介紹了python變量加逗號(hào),的含義,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下 2020-02-02
-
這篇文章主要為大家詳細(xì)介紹了Python中數(shù)據(jù)容器的相關(guān)資料，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)Python有一定的幫助，感興趣的可以了解一下 2022-11-11
-
這篇文章主要介紹了Python 常用的安裝Module方式匯總,需要的朋友可以參考下 2017-05-05
-
利用Python創(chuàng)建第一個(gè)Django框架程序
這篇文章主要介紹了利用Python創(chuàng)建第一個(gè)Django框架程序，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，感興趣的小伙伴可以參考一下 2022-06-06
最新評(píng)論
本文實(shí)例講述了Python排序搜索基本算法之堆排序。分享給大家供大家參考，具體如下：
堆是一種完全二叉樹，堆排序是一種樹形選擇排序，利用了大頂堆堆頂元素最大的特點(diǎn)，不斷取出最大元素，并調(diào)整使剩下的元素還是大頂堆，依次取出最大元素就是排好序的列表。舉例如下，把序列[26,5,77,1,61,11,59,15,48,19]排序，如下：
基于堆的優(yōu)先隊(duì)列算法代碼如下：
def fixUp(a): #在堆尾加入新元素，fixUp恢復(fù)堆的條件
k=len(a)-1
while k>1 and a[k//2]<a[k]:
a[k//2],a[k]=a[k],a[k//2]
k=k//2
def fixDown(a): #取a[1]返回的值，然后把a(bǔ)[N]移到a[1]，fixDown來恢復(fù)堆的條件
k=1
N=len(a)-1
while 2*k<=N:
j=2*k
if j<N and a[j]<a[j+1]:
j+=1
if a[k]<a[j]:
a[k],a[j]=a[j],a[k]
k=j
else:
break
def insert(a,elem):
a.append(elem)
fixUp(a)
def delMax(a):
maxElem=a[1]
N=len(a)
if N<=1:
print('There\'s none element in the list')
return -1
if N==2:
return a[1]
else:
a[1]=a.pop()
fixDown(a)
return maxElem
data=[-1,] #第一個(gè)元素不用，占位
insert(data,26)
insert(data,5)
insert(data,77)
insert(data,1)
insert(data,61)
insert(data,11)
insert(data,59)
insert(data,15)
insert(data,48)
insert(data,19)
result=[]
N=len(data)-1
for i in range(N):
print(data)
result.append(delMax(data))
print(result)
fixUp函數(shù)用于向列表的尾部添加一個(gè)新的元素，然后調(diào)整成大頂堆；fixDown函數(shù)用于取出大頂堆最大的元素后，把列表尾部的元素放到堆頂位置，然后再調(diào)整成大頂堆；insert函數(shù)是每次插入一個(gè)新的元素并調(diào)整成為大頂堆；delMax函數(shù)把最大的元素返回出來并把剩下的元素調(diào)整成為大頂堆。
輸出如下：
[-1, 77, 61, 59, 48, 19, 11, 26, 1, 15, 5] [-1, 61, 48, 59, 15, 19, 11, 26, 1, 5] [-1, 59, 48, 26, 15, 19, 11, 5, 1] [-1, 48, 19, 26, 15, 1, 11, 5] [-1, 26, 19, 11, 15, 1, 5] [-1, 19, 15, 11, 5, 1] [-1, 15, 5, 11, 1] [-1, 11, 5, 1] [-1, 5, 1] [-1, 1] [77, 61, 59, 48, 26, 19, 15, 11, 5, 1]
前面的輸出是不斷取出最大元素后的大頂堆，由于是完全二叉樹，根據(jù)列表可以自己寫出大頂堆的樹形結(jié)構(gòu)，就不在這里贅述，最后一行是排好序的列表。
下面是堆排序算法，代碼如下：
def fixDown(a,k,n): #自頂向下堆化，從k開始堆化
N=n-1
while 2*k<=N:
j=2*k
if j<N and a[j]<a[j+1]: #選出左右孩子節(jié)點(diǎn)中更大的那個(gè)
j+=1
if a[k]<a[j]:
a[k],a[j]=a[j],a[k]
k=j
else:
break
def heapSort(l):
n=len(l)-1
for i in range(n//2,0,-1):
fixDown(l,i,len(l))
while n>1:
l[1],l[n]=l[n],l[1]
fixDown(l,1,n)
n-=1
return l[1:]
l=[-1,26,5,77,1,61,11,59,15,48,19] #第一個(gè)元素不用，占位
res=heapSort(l)
print(res)
輸出如下：
[1, 5, 11, 15, 19, 26, 48, 59, 61, 77]
PS：這里再為大家推薦一款關(guān)于排序的演示工具供大家參考：
在線動(dòng)畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
http://tools.jb51.net/aideddesign/paixu_ys
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》
希望本文所述對大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
-
基于python圖書館管理系統(tǒng)設(shè)計(jì)實(shí)例詳解
這篇文章主要介紹了基于python圖書館管理系統(tǒng)設(shè)計(jì)實(shí)例詳解，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08 - 這篇文章主要介紹了Python 去除字符串中指定字符串,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03
- 這篇文章主要為大家介紹了python庫matplotlib繪制坐標(biāo)圖，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-10-10
-
python實(shí)戰(zhàn)scrapy操作cookie爬取博客涉及browsercookie
這篇文章主要為大家介紹了python實(shí)戰(zhàn)scrapy操作cookie爬取博客涉及browsercookie，下面來學(xué)習(xí)一下 scrapy 操作 Cookie來爬取博客吧2021-11-11 - 今天小編就為大家分享一篇基于Python List的賦值方法，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-06-06
-
python實(shí)現(xiàn)的批量分析xml標(biāo)簽中各個(gè)類別個(gè)數(shù)功能示例
這篇文章主要介紹了python實(shí)現(xiàn)的批量分析xml標(biāo)簽中各個(gè)類別個(gè)數(shù)功能,涉及Python針對xml文件的遍歷、讀取、解析等相關(guān)操作技巧,需要的朋友可以參考下2019-12-12 - 這篇文章主要介紹了python變量加逗號(hào),的含義,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-02-02
- 這篇文章主要為大家詳細(xì)介紹了Python中數(shù)據(jù)容器的相關(guān)資料，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)Python有一定的幫助，感興趣的可以了解一下2022-11-11
- 這篇文章主要介紹了Python 常用的安裝Module方式匯總,需要的朋友可以參考下2017-05-05
-
利用Python創(chuàng)建第一個(gè)Django框架程序
這篇文章主要介紹了利用Python創(chuàng)建第一個(gè)Django框架程序，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，感興趣的小伙伴可以參考一下2022-06-06