Java基础(八) 堆

优先队列

优先队列是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。

和堆的区别

优先队列是一种抽象的数据类型，而堆就是具体的数据结构。也就是说，堆是优先队列的实现之一。

堆

堆是一种特别的二叉树，需要满足以下两个性质才能称为堆。

• 完全二叉树
• 父节点的值始终大于等于或小于等于子节点的值

堆的分类

• 最大堆/大根堆 最大值是根节点
• 最小堆/小根堆 最小值是根节点

堆操作的复杂度

堆的常用方法

小根堆创建

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

大根堆创建

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

创建带初始值的「堆」， 或者称为「堆化」操作，此时的「堆」为「最小堆」。

PriorityQueue<Integer> heapWithValues= new PriorityQueue<>(Arrays.asList(3,1,2));

常用方法

1，插入元素

maxHeap.add();
minHeap.add();

2，获取堆顶元素

// 最小堆获取堆顶元素，即最小值
minHeap.peek();
// 最大堆获取堆顶元素，即最大值
maxHeap.peek();

3，删除堆顶元素

// 最小堆删除堆顶元素
minHeap.poll();
// 最大堆删除堆顶元素
maxheap.poll();

4，获取堆的长度

// 最小堆的长度
minHeap.size();
// 最大堆的长度
maxHeap.size();
// 注意：Java中判断堆是否还有元素，除了检查堆的长度是否为0外，还可以使用isEmpty()方法。
// 如果堆中没有元素，则isEmpty()方法返回true。
// 如果堆中还有元素，则isEmpty()方法返回false。

堆排序

**理论：**堆排序指的是利用堆的数据结构对一组无序元素进行排序。

最小堆排序算法步骤如下：

• 将所有元素堆化成一个最小堆；
• 取出并删除堆顶元素，并将该堆顶元素放置在存储有序元素的数据集T中；
• 此时，堆会调整成新的最小堆；
• 重复 3 和 4 步骤，直到堆中没有元素；
• 此时得到一个新的数据集T，其中的元素按照从小到大的顺序排列。

最大堆排序算法步骤如下：

• 将所有元素堆化成一个最大堆；
• 取出并删除堆顶元素，并将该堆顶元素放置在存储有序元素的数据集T中；
• 此时，堆 会调整成新的 最大堆；
• 重复 3 和 4 步骤，直到堆中没有元素；
• 此时得到一个新的数据集 T，其中的元素按照从大到小的顺序排列。

时间复杂度：O(Nlog N)

空间复杂度：O(N)O(N)

N是堆中的元素个数。