如何使用python堆排序？

大部分小伙伴在学习一段时间


python之后，对python有了一定的了解，所以今天给大家讲一些进阶的内容——堆排序，一起来看看吧~

数据结构

- 堆

介绍堆排序之前，先介绍数据结构

- 堆，堆是一个完全二叉树，并且满足堆的性质：子结点的值总小于（或者大于）其父节点的值。一般来说，堆使用数组来存储，并且根据某个元素在数组中的位置可以推断出其子结点和父节点的位置。

第

n个元素(从0开始计数)的左结点是2*n+1，右结点是2*n+2；其父结点是floor((n - 1)/2)

堆排序的思路

根据堆的定义，根是堆的元素或最小元素。首先，将数组调整为大顶堆，然后是第一个

0个元素就是元素，将第0个和最后一个元素（暂且称为第n个元素）交换位置，然后再将0~n-1个元素调整为堆，将第0个元素和第n-1元素交换，依次循环下去~

听起来很复杂，但是只要你花一点时间，看完这篇文章，你肯定能理解堆排序。让我们拆解一下

~

如何将数组调整为堆

思路：从最后一个节点的父节点开始处理，假设一共有

n个元素，那么最后一个结点的父节点是第(n-1)/2个元素，找到其子节点中值节点，然后根其自身比较，如果自身值比子节点小，那么交换位置。

循环上述过程，从第

(n-1)/2 一直遍历到第0个元素就完成了堆的构建。

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])

完整逻辑

建堆是堆排序的重要步骤之一。建立堆后，第一个

0个元素和最后一个元素交换位置，然后将前n-1个元素构建堆，再将第0个和倒数第二个交换...

涉及到一些细节，只有自己编码才能掌握。这是一个副本

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)

输出结果：

如需了解更多


python实用知识，点击进入
。