堆排序堆排序（heapsort）是一种基于堆数据结构实现的高效排序算法。我们可以利用已经学过的“建堆操作”和“元素出堆操作”实现堆排序。输入数组并建立小顶堆，此时最小元素位于堆顶。不断执行出堆操作，依次记录出堆元素，即可得到从小到大排序的序列。以上方法虽然可行，但需借助一

1.需要具备的知识1.1以顺序存储方式存储完全二叉树完全二叉树:节点从上到下，从左到右布局的二叉树，如下图所示。完全二叉树可以使用类似数组这种顺序存储的结构存节点，如下图。按照"层级遍历"方式遍历这棵树(还有"前序、中序、后序"遍历方式，这里不做介绍)，遍历结果"10->5->1->2-

堆堆（heap）是一种满足特定条件的完全二叉树，主要分为两种类型：小顶堆（minheap）：任意节点的值≤其子节点的值大顶堆（maxheap）：任意节点的值≥其子节点的值堆作为完全二叉树的一个特例，具有以下特性：最底层节点靠左填充，其他层的节点都被填满我们将二叉树的根节点称为“堆顶”，将

堆堆就像是山川的峰峦，它们层叠起伏、形态各异。每一座山峰都有其高低之分，而最高的山峰总是最先映入眼帘。8.1堆「堆heap」是一种满足特定条件的完全二叉树，主要可分为图8‑1所示的两种类型。‧「大顶堆maxheap」：任意节点的值≥其子节点的值。‧「小顶堆minheap」

1.简介堆是一种特殊的数据结构，通常用于实现优先队列。堆是一个可以被看作近似完全二叉树的结构，并且具有一些特殊的性质，根据这些性质，堆被分为最大堆（或者大根堆，大顶堆）和最小堆两种。2.基本性质完全二叉树结构：堆必须是一棵完全二叉树，即除了最底层，其他层都是满的，而且最底层的节点都尽量

将数组以\(O(n)\)的时间复杂度和\(O(1)\)的空间复杂度构造为堆的trick。想象我们把数组随意地填充进一棵完全二叉树（尚不满足堆的性质），然后通过交换节点等操作把二叉树变成堆。因为完全二叉树的节点个数性质，我们直接从\(\dfrac{n}{2}\)到\(1\)倒序遍历（相当于从下到上遍历