堆
1 堆的定义
堆：是一类特殊的数据结构的统称，通常可以被看做是一颗完全二叉树的数组对象。
堆的特性
-
完全二叉树。除了树的最后一层节点不需要是满的，其他每一层从左到右都是满的，如果最后一层节点不是满的，那么要求左满右不满。
-
数组实现
如果一个结点的位置为k，则它的父结点的位置为[k/2],而它的两个子结点的位置则分别为2k和2k+1。
-
每个节点都大于等于它的两个子节点。这里要注意堆中仅仅规定了每个节点大于等于它的两个子节点，但这两个子节点的顺序并没有做规定，跟之前学习的二叉查找树是有区别的。
2 堆的API设计
package study.algorithm.heap;
public class Heap<T extends Comparable<T>> {
//存储堆中的元素
private T[] items;
//记录堆中元素的个数
private int N;
public Heap(int capacity) {
this.items = (T[]) new Comparable[capacity + 1];
this.N = 0;
}
public int size() {
return this.N;
}
public T get(int i) {
return items[i];
}
//判断堆中索引i处的元素是否小于索引j处的元素
private boolean less(int i, int j) {
return items[i].compareTo(items[j]) < 0;
}
//交换堆中i索引和j索引处的值
private void swap(int i, int j) {
T temp = items[i];
items[i] = items[j];
items[j] = temp;
}
//往堆中插入元素
public void insert(T t) {
items[++N] = t;
swim(N);
}
//使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
private void swim(int k) {
//通过循环不断比较当前节点和父节点的值。如果发现父节点的值比当前节点的值小，则交换位置
while (k > 1) {
if (less(k / 2, k)) {
swap(k / 2, k);
k = k / 2;
continue;
} else {
break;
}
}
}
//删除堆中最大的元素，并返回这个最大元素
public T delMax() {
T max = items[1];
//交换索引i处的元素和最大索引处的元素，让完全二叉树中最底层最右侧的元素变为临时根节点
swap(1, N);
//删除最大索引处的元素
items[N] = null;
//元素个数-1
N--;
//通过下沉算法，调整堆，让堆重新有序
sink(1);
return max;
}
//使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
private void sink(int k) {
//通过循环不断对比当前k节点和其子节点2k以及2k+1处中较大值的元素大小。如果当前节点小，则交换位置
while (2 * k <= N) {
//获取当前节点的子节点中的较大节点
int max;//记录较大节点所在索引值
if (items[2 * k + 1] == null) {
max = 2 * k;
} else {
max = less(2 * k, 2 * k + 1) ? 2 * k + 1 : 2 * k;
}
//比较当前节点和较大节点的值
if (less(k, max)) {
swap(max, k);
k = max;
continue;
} else {
break;
}
}
}
}
3 堆排序
package study.algorithm.heap;
public class HeapSort {
//数组从小到大排序
public static void sort(Comparable[] a) {
//构建堆
Comparable[] heap = new Comparable[a.length + 1];
createHeap(a, heap);
//定义一个变量，记录未排序的元素中最大的索引
int N = heap.length - 1;
//通过循环，交换1索引处的元素和未排序的元素中最大的索引处的元素
while (N != 1) {
//交换元素
swap(heap, 1, N);
//排序交换后最大元素所在的索引，让它不要参与堆的下沉调整
N--;
//需要对索引1处的元素进行堆的下沉调整
sink(heap, 1, N);
}
//把heap中的数据复制到原数组中
System.arraycopy(heap, 1, a, 0, a.length);
}
//根据原数组source，构造出堆heap
private static void createHeap(Comparable[] source, Comparable[] heap) {
//把source中的元素拷贝到heap中，此时heap中的元素就形成一个无序的堆
System.arraycopy(source, 0, heap, 1, source.length);
//对堆中的元素做下沉调整（从长度的一半处开始，往索引处1处扫描）
for (int i = heap.length / 2; i > 0; i--) {
sink(heap, i, heap.length - 1);
}
}
//在 heap 堆中，对 target 处的元素做下沉，范围是 0-range
private static void sink(Comparable[] heap, int target, int range) {
while (2 * target <= range) {
int max;
if (2 * target == range) {
max = 2 * target;
} else {
max = less(heap[2 * target], heap[2 * target + 1]) ? 2 * target + 1 : 2 * target;
}
if (less(heap[target], heap[max])) {
swap(heap, target, max);
target = max;
} else {
break;
}
}
}
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
private static void swap(Comparable[] heap, int i, int j) {
Comparable temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
}
堆排序算法分析
- 下沉算法复杂度为O(logn)，堆排序的时间复杂度O(NlogN)，额外空间复杂度O(1)，是一个不稳定的排序算法
优先队列
优先队列按照其作用不同，可以分为一下两种：
最大优先队列：
- 可以获取并删除队列中最大的值
最小优先队列：
- 可以获取并删除队列中最小的值
1 最大优先队列
基于堆实现最大优先队列
API实现与堆实现一模一样
package study.algorithm.priority;
public class MaxPriorityQueue<T extends Comparable<T>> {
//存储堆中的元素
private T[] items;
//记录堆中元素的个数
private int N;
public MaxPriorityQueue(int capacity) {
this.items = (T[]) new Comparable[capacity + 1];
this.N = 0;
}
public int size() {
return this.N;
}
public boolean isEmpty() {
return this.N == 0;
}
private boolean less(int i, int j) {
return items[i].compareTo(items[j]) < 0;
}
private void swap(int i, int j) {
T temp = items[i];
items[i] = items[j];
items[j] = temp;
}
public void insert(T t) {
items[++N] = t;
swim(N);
}
public T delMax() {
T max = items[1];
swap(1, N);
N--;
sink(1);
return max;
}
//使用上浮算法，使索引k处的元素在堆中处于一个正确的位置
private void swim(int k) {
while (k > 1) {
if (less(k / 2, k)) {
swap(k / 2, k);
k = k / 2;
} else {
break;
}
}
}
//使用下沉算法，使索引k处的元素在堆中处于一个正确的位置
private void sink(int k) {
while (2 * k <= N) {
int max;
if (2 * k == N) {
max = 2 * k;
} else {
max = less(2 * k, 2 * k + 1) ? 2 * k + 1 : 2 * k;
}
if (less(k, max)) {
swap(k, max);
k = max;
} else {
break;
}
}
}
}
2 最小优先队列
最小优先队列同样是基于堆实现的，满足两个特性：
- 最小的元素放在数组的索引1处
- 每个节点的数据总是小于等于它的两个子节点的数据
package study.algorithm.priority;
public class MinPriorityQueue<T extends Comparable<T>> {
//存储堆中的元素
private T[] items;
//记录堆中元素的个数
private int N;
public MinPriorityQueue(int capacity) {
this.items = (T[]) new Comparable[capacity + 1];
this.N = 0;
}
public int size() {
return this.N;
}
public boolean isEmpty() {
return this.N == 0;
}
private boolean less(int i, int j) {
return items[i].compareTo(items[j]) < 0;
}
private void swap(int i, int j) {
T temp = items[i];
items[i] = items[j];
items[j] = temp;
}
public void insert(T t) {
items[++N] = t;
swim(N);
}
public T delMin() {
T min = items[1];
swap(1, N);
N--;
sink(1);
return min;
}
//使用上浮算法，使索引k处的元素在堆中处于一个正确的位置
private void swim(int k) {
while (k > 1) {
if (less(k, k / 2)) {
swap(k / 2, k);
k = k / 2;
} else {
break;
}
}
}
//使用下沉算法，使索引k处的元素在堆中处于一个正确的位置
private void sink(int k) {
while (2 * k <= N) {
int min;
if (2 * k == N) {
min = 2 * k;
} else {
min = less(2 * k, 2 * k + 1) ? 2 * k : 2 * k + 1;
}
if (less(min, k)) {
swap(k, min);
k = min;
} else {
break;
}
}
}
}
3 索引优先队列
在之前实现的最大优先队列和最小优先队列，他们可以分别快速访问到队列中最大元素和最小元素，但是他们有一个缺点，就是没有办法**通过索引访问已存在于优先队列中的对象，并更新它们。**为了实现这个目的，在优先队列的基础上，学习一种新的数据结构，索引优先队列。接下来我们以最小索引优先队列举列。
索引优先队列实现思路
步骤1
可以用一个T[] items数组来保存数据元素，在insert(int k,T t)完成插入时，可以把k看做是items数组的索引，把t元素放到items数组的索引k处，这样我们再根据k获取元素t时就很方便了，直接就可以拿到items[k]即可。
步骤2
items数组中的元素顺序是随机的，并不是堆有序的，所以，为了完成这个需求，我们可以增加一个数组int[]pq,来保存每个元素在items数组中的索引，pq数组需要堆有序，也就是说，pq[1]对应的数据元素items[pq[1]]要小于等于pq[2]和pq[3]对应的数据元素items[pq[2]]和items[pq[3]]。
步骤3
我们可以发现，其实我们通过上浮和下沉做堆调整的时候，其实调整的是pq数组。如果需要对items中的元素进行修改，比如让items[0]=“H”,那么很显然，我们需要对pq中的数据做堆调整，而且是调整pq[9]中元素的位置。但现在就会遇到一个问题，我们修改的是items数组中0索引处的值，如何才能快速的知道需要挑中pq[9]中元素的位置呢？
最直观的想法就是遍历pq数组，拿出每一个元素和0做比较，如果当前元素是0，那么调整该索引处的元素即可，但是效率很低。
我们可以另外增加一个数组，int[] qp,用来存储pq的逆序。
当有了pq数组后，如果我们修改items[0]=“H”，那么就可以先通过索引0，在qp数组中找到qp的索引：qp[0]=9,那么直接调整pq[9]即可。
索引优先队列API实现
package study.algorithm.priority;
public class IndexMinPriorityQueue<T extends Comparable<T>> {
//用来存储元素的数组
private T[] items;
//保存每个元素在items数组中的索引，pq数组堆有序
private int[] pq;
//保存pq的逆序，pq的值作为索引，pq的索引作为值
private int[] qp;
//记录堆中元素的个数
private int N;
public IndexMinPriorityQueue(int capacity) {
this.items = (T[]) new Comparable[capacity + 1];
this.pq = new int[capacity + 1];
this.qp = new int[capacity + 1];
this.N = 0;
//默认情况下，队列中没有存储任何数据，让qp中的元素都为-1
for (int i = 0; i < qp.length; i++) {
qp[i] = -1;
}
}
public int size() {
return N;
}
public boolean isEmpty() {
return N == 0;
}
public boolean contains(int k) {
return qp[k] != -1;
}
//最小元素关联的索引
public int minIndex() {
return pq[1];
}
public void insert(int i, T t) {
//判断i是否被关联。如果已经被关联，则不让插入
if (contains(i)) {
return;
}
//元素个数+1
N++;
//把数据存储到items对应的i位置处
items[i] = t;
//把i存储到pq中
pq[N] = i;
//通过qp来记录pq中的i
qp[i] = N;
//通过上浮算法调整堆
swim(N);
}
public int delMin() {
//获取最小元素关联的索引
int minIndex = pq[1];
//交换pq中索引1处和最大索引处的元素
swap(1, N);
//删除pq中对应的内容
qp[pq[N]] = -1;
//删除pq中最大索引处的内容
pq[N] = -1;
//删除items中对应的内容
items[minIndex] = null;
//元素个数-1
N--;
//下沉调整
sink(1);
return minIndex;
}
public void delete(int i) {
//找到i在pq中的索引
int k = qp[i];
//交换pq中索引k处的值和索引N处的值
swap(k, N);
//删除qp中的内容
qp[pq[N]] = -1;
//删除pq中的内容
pq[N] = -1;
//删除items中的内容
items[k] = null;
//元素的数量-1
N--;
//堆的调整
sink(k);
swim(k);
}
//修改索引i处的元素为t
public void changeItem(int i, T t) {
//修改items数组中i位置的元素为t
items[i] = t;
//找到i在pq中出现的位置
int k = qp[i];
//堆调整
sink(k);
swim(k);
}
private void swim(int k) {
while (k > 1) {
if (less(k, k / 2)) {
swap(k, k / 2);
k = k / 2;
} else {
break;
}
}
}
private void sink(int k) {
while (2 * k <= N) {
int min;
if (2 * k == N) {
min = 2 * k;
} else {
min = less(2 * k, 2 * k + 1) ? 2 * k : 2 * k + 1;
}
if (less(k, min)) {
break;
}
swap(k, min);
k = min;
}
}
private boolean less(int i, int j) {
return items[pq[i]].compareTo(items[pq[j]]) < 0;
}
private void swap(int i, int j) {
//交换pq中的数据
int temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
//更新qp中的数据
qp[pq[i]] = i;
qp[pq[j]] = j;
}
}