初学数据结构堆和优先队列
在这里我给各位举四个不同的树的例子。它们分别是堆、线段树、字典树以及并查集。那么通过这些不同树的结构学习，可以体会到数据结构的灵活之处，以及我们在设计数据结构的时候其中的一些思考。
优先队列
优先队列本身也是一种队列，对于和普通队列的先进先出的结构有所不同，主要区别在于出队操作上，出队顺序和入队顺序无关，而是跟元素的优先级密切相关。典型的例子：系统中同时执行多个任务，并为多个任务去分配CPU的时间片，此时系统就要看各个任务的优先级，去动态的选择优先级最高的任务去执行。
什么是动态
在这里呢，我简单画了一个示意图，如下图所示：
假设有一个任务处理中心，现在有三个任务请求，而这个任务处理中心可能就需要先要找出这些任务请求中优先级最高的那个请求，相应的进行处理。再处理完这个任务的同时，很有可能又来了很多新的任务请求，这时候要随时根据新来的任务的情况，调整整个队列的优先级，这就是动态。因此任务处理中心并不是一开始就知道所有的任务是什么，排排序就好了。而是随着时间的推移，会不停的有新元素入队，也就是队列中的元素是在不断变化，所以我们必须使用一个优先队列这样的数据结构来解决问题。
优先队列的时间复杂度
针对优先队列这样的一种结构，我们也是可以使用不同的底层实现。
- 无论是数组还是是链表，都可以直接用这种普通的线性结构充当优先队列的实现方式。
- 也可以使用顺序线性结构。而顺序线性结构是指整个线性结构一直维持所有的元素的顺序。换句话说，整个线性结构一直是从小到大排列或者从大到小排列。
- 甚至我们可以使用堆这种数据结构来实现优先队列。对于入队操作和出队操作，可以做到是O(logn)这个级别的复杂度，而且和之前讲的二分搜索树平均在O(logn)这个级别不同，堆可以在最差的情况下都是O(logn)这个级别。这使得堆这种数据结构是相当高效的。
入队 出队（拿出最大元素）
普通线性结构
O(1)
O(n)
顺序线性结构
O(n)
O(1)
堆
O(logn)
O(logn)
基于堆的优先队列实现
优先队列的代码实现
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> { private MaxHeap<E> maxHeap;
public PriorityQueue(){
maxHeap = new MaxHeap();
}
@Override
public void enqueue(E e) {
maxHeap.add(e);
}
@Override
public E dequeue() {
return maxHeap.extractMax();
}
@Override
public E getFront() {
return maxHeap.findMax();
}
@Override
public int getSize() {
return maxHeap.getSize();
}
@Override
public boolean isEmpty() {
return maxHeap.isEmpty();
}
}
总结
在这一小节，我就简单的介绍了什么是优先队列，并且引出了我们可以使用堆这种数据结构作为优先队列的底层实现，完成一个高效的优先队列这样的数据结构。
堆
二叉堆
二叉堆的性质
- 二叉堆是一棵完全二叉树
- 堆中某个节点的值总是不大于其父节点的值(最大堆)，或者是堆堆中某个节点的值总是不小于其父节点的值(最小堆)
二叉堆的种类
- 最大堆：父结点的键值总是大于或等于任何一个子节点的键值;
- 最小堆：父结点的键值总是小于或等于任何一个子节点的键值。
二叉堆的构建(Heapify)
构建二叉堆，是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点依次下沉sift down。其算法复杂度则是O(nlogn)。
- 首先，我们从最后一个非叶子节点开始，也就是从节点22开始。如果节点22小于于它左右孩子中最大的一个，则节点22下沉。
- 接下来轮到节点13，如果节点13小于它左右孩子中最大的一个，则节点13下沉。
- 接下来轮到节点19，如果节点19小于它左右孩子中最大的一个，则节点19下沉。
- 接下来轮到节点17，如果节点17小于它左右孩子中最大的一个，则节点17下沉。
- 节点15继续比较，继续下沉。
- 这样一来，一颗无序的完全二叉树就构建成了一个最大堆。
过程如下图所示：
示例代码：
public MaxHeap(E[] arr){ data = new Array<>(arr);
// 对最后一个节点的父亲节点 作下沉操作
for(int i = parent(arr.length -1); i >= 0; i--){
siftDown(i);
}
}
二叉堆的插入操作
从堆的角度看，向堆中添加一个元素这个过程，可以称之为sift up（上浮）。
- 二叉堆的节点插入，插入位置是完全二叉树的最后一个位置。比如我们插入一个新节点，值是 52。
- 这时候，我们让节点52的父节点16做比较，如果52>16，则让新节点“上浮”，和父节点交换位置。
- 继续用节点52和父节点41做比较，如果52>41，则让新节点继续“上浮”。
- 继续比较，最终新节点52<62，此时sift up操作就结束了。
过程如下图所示：
示例代码：
// 筛选(上浮)元素,使满足 堆中某个节点的值总是不大于其父节点的值private void siftUp(int k){
// 父节点和子节点做比较，父元素要小的话，交换父子元素
while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
data.swap(k, parent(k));
// 同时替换索引
k = parent(k);
}
}
// 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
private int parent(int index){
if(index == 0){
throw new IllegalArgumentException("index-0 doesn"t have parent");
}
return (index - 1) / 2;
}
二叉堆的删除操作
对于堆来说，之所以管它叫做最大堆，是因为每次从堆中取出元素，只取出堆顶的元素，也就是这棵二叉树的根节点所在的这个元素。
- 二叉堆的节点删除过程和插入过程正好相反，所删除的是处于堆顶的节点。比如我们删除最大堆的堆顶节点62。
- 这时候，为了维持完全二叉树的结构，我们把堆的最后一个节点16补到原本堆顶的位置。
- 接下来我们让移动到堆顶的节点16和它左右孩子进行比较，如果左右孩子中最大的一个（显然是左节点52）比节点16大，那么让节点16“下沉”。
- 继续让节点16和它的左右孩子做比较，左右孩子中最大的是节点41，由于16<41，让节点16继续“下沉”。
- 继续让节点16和它的左右孩子做比较，此时满足最大堆的性质，结束sift down操作。
- 这样一来，二叉堆重新得到了调整。
过程如下图所示：
示例代码：
// 筛选(下沉)元素,使满足 堆中某个节点的值总是不大于其父节点的值private void siftDown(int k){
// k节点所在的索引 比 data的总数还要小
while(leftChild(k) < data.getSize()){
int j = leftChild(k);
// 判断有右孩子，并且比较左右孩子的大小
if(j + 1 < data.getSize() &&
data.get(j + 1).compareTo(data.get(j)) > 0){
j = rightChild(k);
// data[j] 是leftChild和rightChild中的最大值
}
// k是头节点比左右孩子都要大即可中断
if(data.get(k).compareTo(data.get(j)) >= 0){
break;
}
data.swap(k ,j);
k = j;
}
}
最大堆的代码实现
public class MaxHeap<E extends Comparable<E>> { private Array<E> data;
public MaxHeap(int capacity){
data = new Array<>(capacity);
}
public MaxHeap(){
data = new Array<>();
}
public MaxHeap(E[] arr){
data = new Array<>(arr);
// 对最后一个节点的父亲节点 作 下沉操作
for(int i = parent(arr.length -1); i >= 0; i--){
siftDown(i);
}
}
// 返回堆中的元素个数
public int getSize(){
return data.getSize();
}
// 返回一个布尔值，表示堆中是否为空
public boolean isEmpty(){
return data.isEmpty();
}
// 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
private int parent(int index){
if(index == 0){
throw new IllegalArgumentException("index-0 doesn"t have parent");
}
return (index - 1) / 2;
}
// 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的 索引
private int leftChild(int index){
return index * 2 + 1;
}
// 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的 索引
private int rightChild(int index){
return index * 2 + 2;
}
// 向堆中添加元素
public void add(E e){
data.addLast(e);
siftUp(data.getSize() - 1);
}
// 筛选(上浮)元素,使满足 堆中某个节点的值总是不大于其父节点的值
private void siftUp(int k){
// 父节点和子节点做比较，父元素要小的话，交换父子元素
while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
data.swap(k, parent(k));
// 同时替换索引
k = parent(k);
}
}
// 看堆中最大元素
public E findMax(){
if(data.getSize() == 0){
throw new IllegalArgumentException("Can not findMax when heap is empty.");
}
return data.get(0);
}
// 取出堆中最大元素
public E extractMax(){
E ret = findMax();
data.swap(0, data.getSize() - 1);
data.removeLast();
siftDown(0);
return ret;
}
private void siftDown(int k){
// k节点所在的索引 比 data的总数还要小
while(leftChild(k) < data.getSize()){
int j = leftChild(k);
// 判断有右孩子，并且比较左右孩子的大小
if(j + 1 < data.getSize() &&
data.get(j + 1).compareTo(data.get(j)) > 0){
j = rightChild(k);
// data[j] 是leftChild和rightChild中的最大值
}
// k是头节点比左右孩子都要大即可中断
if(data.get(k).compareTo(data.get(j)) >= 0){
break;
}
data.swap(k ,j);
k = j;
}
}
}
总结
在这一章从一个更广义的角度来理解了优先队列，并拓展了优先队列的定义。比如普通队列的先到先得，优先队列（拿出优先级最高的那个元素作为出队的元素）这样的队列。
以上是 初学数据结构堆和优先队列 的全部内容， 来源链接： utcz.com/z/513557.html
