什么是优先队列
一个普通队列在删除时，删除最大或者最小的元素
方法定义
| 方法 | |
|---|---|
| MaxPQ() | 创建一个空队列 |
| MaxPQ(Key[] a) | 创建一个具有初始化数据的队列 |
| void insert(Key v) | 插入 |
| Key delMax() | 删除最大元素，并返回该元素 |
| boolean isEmpty() | 是否为空 |
| Key max() | 返回最大元素 |
| int size() | 返回队列大小 |
二叉树(后面将之成为堆)
节点为N的二叉树，高度为lgN
大(小)顶堆
每一个父节点都不小于它的子节点
数组实现二叉树结构
以索引1作为起始，1的位置存储根结点，节点n的子节点为2n,2n+1，节点k的子节点为k/2
屏幕快照 2018-08-14 下午4.55.41.png
节点的提升
首先针对单个节点进行处理
循环比较，它与它的父节点，若大于父节点则进行交换。
private void swim(int k)
{
while (k > 1 && less(k/2, k))
{
exch(k, k/2);
k = k/2;
}
}
节点的插入
public void insert(Key x)
{
pq[++N] = x;
swim(N);
}
节点的下降
若节点小于子节点，则将次节点循环下降
private void sink(int k)
{
while (2*k <= N)
{
int j = 2*k;
if (j < N && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
删除最大元素
将最顶部元素与末尾元素交换，而后输出末尾元素，并且将交换后的顶部元素再进行sink
public Key delMax()
{
Key max = pq[1];
exch(1, N--);
sink(1);
pq[N+1] = null;
return max;
}
算法复杂度分析
| 方法 | 复杂度 |
|---|---|
| insert | logN |
| delMax | logN |
堆排序
思路
- 构造一个大顶堆，取堆顶元素，将堆顶元素与最后一个元素交换。
- 将剩余元素重新构成一个大顶堆
代码实现
public class Heap
{
public static void sort(Comparable[] a)
{
int N = a.length;
for (int k = N/2; k >= 1; k--)
sink(a, k, N);
while (N > 1)
{
exch(a, 1, N);
sink(a, 1, --N);
}
}
}
算法复杂度与特点分析
- 堆排序的算法复杂度为2NlogN,最坏为2NlogN，最好为NlogN
- 它是一个占用额外空间很小的算法
- 它是一个不稳定算法
