深入解析堆排序

文章目录

• 堆

• • 一、堆的定义

  • 二、堆的构建

  • • 1、数据结构选型
    • 2、初始化
    • 3、添加元素
    • 4、删除元素

  • 三、PriorityQueue

  • 四、堆排序

  • • 1、让无序数组堆化
    • 2、借助大根堆进行排序

堆

一、堆的定义

数据结构中的堆，不要和 jvm 中的堆空间搞混了

在数据结构中，大根堆 和小根堆 属于同一类数据存储方式，并且均表现为一棵完全二叉树 。具体来说，在大根堆 中，默认情况下每个节点的值都不小于其子节点对应的数值；而相应地，在小根堆 中，则相反

完全二叉树指的是这样一种结构：它是一棵满二叉树，并且所有的叶节点都均匀地排列在最底层

如何定义满二叉树？

在后续讲解中（如有特殊说明除外），主要采用大根堆进行讲解相信你很快就能写出小根堆的代码。

大根堆：

小根堆：

![小根堆](https://ad.itadn.com/c/weblog/bl