堆排序菜鸟教程,堆排序怎么排序

　　学习python一段时间后，大部分朋友对python有了一定的了解。所以今天我们来说一些高级内容3354堆排序。来看看吧~

　　数据结构 - 堆

　　在介绍堆排序之前，先介绍一下数据结构——堆。Heap是一棵完全的二叉树，它满足heap的性质：子节点的值总是小于(或大于)其父节点的值。一般来说，堆存储在一个数组中，它的子节点和父节点的位置可以从数组中一个元素的位置推断出来。

　　第n个元素(从0开始数)的左节点是2 * n ^ 1，右节点是2 * n2它的父节点是floor((n-1)/2)

　　堆排序的思路

　　根据堆的定义，根是堆的元素或最小元素。首先，将数组调整到顶部堆，然后第0个元素是元素。在第0个和最后一个元素(暂称为第n个元素)之间交换位置，然后将第0~n-1个元素调整到堆中，将第0个元素与第n-1个元素交换，依次循环下去~

　　这听起来很复杂，但是只要你花点时间读一读这篇文章，你就一定能理解堆排序。下面我们稍微拆解一下吧~

　　如何将数组调整为堆

　　 style="text-align:justify;text-justify:inter-ideograph">思路：从最后一个结点的父节点开始处理，假设一共有n个元素，那么最后一个结点的父节点是第(n-1)/2个元素，找到其子节点中值节点，然后根其自身比较，如果自身值比子节点小，那么交换位置。

循环上述过程，从第(n-1)/2 一直遍历到第0个元素就完成了堆的构建。

Python代码如下所示：

defmake_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)andarray[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-*-
　　
　　importmath
　　
　　defmake_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<nandarray[child]>array[last_p]):
　　
　　tmp=array[last_p]
　　
　　array[last_p]=array[child]
　　
　　array[child]=tmp
　　
　　last_p=last_p-1
　　
　　defswap_i_j(array,i,j):
　　
　　array[i],array[j]=array[j],array[i]
　　
　　defheap_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实用知识，点击进入PyThon学习网教学中心。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

相关文章阅读