Python|一览小顶堆
前言
堆排序是指利用堆这种数据结构所设计的一种排序算法。本节将以小堆顶为例来进行介绍。
问题描述
堆是一种完全二叉树(一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。)的结构。以本次所讲的小顶堆为例,小堆顶是指其任意父节点的数据值均不大于其左子节点和右子节点的值。以如数组[4,6,8,5,9]为例:
解决方案
再对上面的例子进行解释,以小顶堆为例,首先需要将无需序列构建成一个堆,根据升序降序需求选择为小顶堆,然后需要将最大元素"沉"到数组末端,以此类推,将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端。
结语
本文简单的介绍了堆排序中小顶堆的排序,并以一个数组作为例子进行讲解。下节我们会进一步介绍堆排序。
作者:文裕龙
实习编辑:衡辉
稿件来源:深度学习与文旅应用实验室(DLETA)
赞 (0)