python堆排序的使用方法

這篇文章將為大家詳細(xì)講解有關(guān)python堆排序的使用方法，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

數(shù)據(jù)結(jié)構(gòu) - 堆

介紹堆排序之前，先介紹數(shù)據(jù)結(jié)構(gòu) - 堆，堆是一個(gè)完全二叉樹，并且滿足堆的性質(zhì)：子結(jié)點(diǎn)的值總小于（或者大于）其父節(jié)點(diǎn)的值。一般來說，堆使用數(shù)組來存儲(chǔ)，并且根據(jù)某個(gè)元素在數(shù)組中的位置可以推斷出其子結(jié)點(diǎn)和父節(jié)點(diǎn)的位置。

第n個(gè)元素(從0開始計(jì)數(shù))的左結(jié)點(diǎn)是2*n+1，右結(jié)點(diǎn)是2*n+2；其父結(jié)點(diǎn)是floor((n - 1)/2)

堆排序的思路

根據(jù)堆的定義可知，根是堆的最大元素或者最小元素，首先將數(shù)組調(diào)整為大頂堆，那么第0個(gè)元素就是最大元素，將第0個(gè)和最后一個(gè)元素（暫且稱為第n個(gè)元素）交換位置，然后再將0~n-1個(gè)元素調(diào)整為堆，將第0個(gè)元素和第n-1元素交換，依次循環(huán)下去~

聽起來很復(fù)雜，但只要花點(diǎn)時(shí)間，讀完這篇文章，一定可以明白堆排序，下面一點(diǎn)點(diǎn)拆解~

如何將數(shù)組調(diào)整為堆

思路：從最后一個(gè)結(jié)點(diǎn)的父節(jié)點(diǎn)開始處理，假設(shè)一共有n個(gè)元素，那么最后一個(gè)結(jié)點(diǎn)的父節(jié)點(diǎn)是第(n-1)/2個(gè)元素，找到其子節(jié)點(diǎn)中值最大的節(jié)點(diǎn)，然后根其自身比較，如果自身值比子節(jié)點(diǎn)小，那么交換位置。

循環(huán)上述過程，從第(n-1)/2 一直遍歷到第0個(gè)元素就完成了堆的構(gòu)建。

Python代碼如下所示：

def make_heap(array):
last_p = (len(array)-1)/2
while(last_p>=0):
child = 2*last_p+1
if(child+1 < len(array)):
if(array[child] < array[child+1]):
child = child+1
if(child < len(array) and array[child] > array[last_p]):
tmp = array[last_p]
array[last_p] = array[child]
array[child] = tmp
last_p=last_p-1
print(array[0])

完整邏輯

構(gòu)建堆是堆排序中重要環(huán)節(jié)之一，構(gòu)建完堆之后應(yīng)該將第0個(gè)元素和最后一個(gè)元素交換位置，然后將前n-1個(gè)元素構(gòu)建堆，再將第0個(gè)和倒數(shù)第二個(gè)交換...

其中涉及到一些細(xì)節(jié)，只有自己親自動(dòng)手編碼才能掌握了解，這里給出一份DEMO

完整代碼如下：

# -*- coding: UTF-8 -*-
 
import math
 
def make_heap(array,n):
 
last_p = (n-1)/2
 
while(last_p>=0):
 
child = 2*last_p+1
 
if(child+1 < n):
 
if(array[child] < array[child+1]):
 
child = child+1
 
if(child < n and array[child] > array[last_p]):
 
tmp = array[last_p]
 
array[last_p] = array[child]
 
array[child] = tmp
 
last_p=last_p-1
 
def swap_i_j(array,i,j):
 
array[i],array[j] = array[j],array[i]
 
def heap_sort(array):
 
n = len(array)
 
while(n>0):
 
make_heap(array,n)
 
print(n,array)
 
swap_i_j(array,0,n-1)
 
print(n,array)
 
n = n-1
 
array = [16,7,8,20,17,3]
 
heap_sort(array)
 
print(array)

輸出結(jié)果：

關(guān)于python堆排序的使用方法就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。