堆排序及优先队列

在做leetcode时碰到了应用PriorityQueue，巩固一下相关知识

• 数据结构
  • 优先队列
  • 自主实现的堆结构

堆

堆作为一种非线性数据结构，既可以被视作数组形式，也可以被理解为一种完全二叉树的表示方式。实际上，堆是通过完全二叉树的特性来组织和管理的一维数组。根据其特性，堆可以划分为大顶堆与小顶堆两种类型。这种结构具有重要的应用价值，常被用于实现优先队列的功能，因为它能够高效地获取当前最为关键的元素。

在构建堆的过程中，其时间复杂度为O（N），且仅需调用一次即可完成。对于堆排序而言，每次操作均涉及将堆顶元素与末尾元素进行交换，并对堆进行相应的调整，该过程的时间复杂度为O（logN）。而在向堆中插入新元素时，则需要将该元素放置于数组末尾，并通过向上比较的方式寻找合适的位置以维持堆的性质，这一操作的时间复杂度同样为O（logN）。

大顶堆：所有节点的值均不小于其左右子节点的值

小顶堆是一种数据结构，其中每一个节点的数值均不大于其对应左右子节点的数值。

![在这里插入图片描述](https://cdl.itadn.